Efa & Her Array

adnan_toky Father Timm Memorial Prog...
Limits 2s, 512 MB

Efa has received an array a1,a2,a3,ana_1, a_2, a_3, \dots a_n of nn integers as her birthday gift. Her younger sister Tahia is fond of GCD (Greatest Common Divisor) and her elder sister Sifa likes LCM (Least Common Multiple). She wants to select a subarray from the array to please her sisters. She wants to make a choice such that when she multiplies the GCD of all elements in the chosen subarray with her favorite number kk, she will get the LCM of all elements in that subarray. Efa wants to know the number of subarrays she can select from the given array that satisfy this condition, can you help her with that?

Formally, you have to count the pair of integers (ii, jj) such that 1ijn1 \leq i \leq j \leq n and LCM(ai,ai+1,,aj)\text{LCM}(a_i, a_{i+1}, \dots , a_j) == k×GCD(ai,ai+1,,aj)k \times \text{GCD}(a_i, a_{i+1}, \dots , a_j).

Input

The first line of the input contains an integer tt (1t100001 \leq t \leq 10000) denoting the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers nn and kk (1n1051 \leq n \leq 10^5, 1k1001 \leq k \leq 100) - the size of Efa’s array and her favorite number.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1001 \leq a_i \leq 100).

Subtask 1 (10 Points): Sum of nn over all test cases doesn’t exceed 100100.

Subtask 2 (20 Points): Sum of nn over all test cases doesn’t exceed 10001000.

Subtask 3 (70 Points): Sum of nn over all test cases doesn’t exceed 10510^5.

Output

For each test case, print a single integer - the number of subarrays satisfying the condition.

Sample

InputOutput
3
5 1
3 1 3 3 2
5 2
1 2 1 2 1
5 3
3 9 5 4 7
6
10
1

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.