Efa & Her Array

Efa has received an array $a_1, a_2, a_3, \dots a_n$ of $n$ 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 $k$, 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 ($i$, $j$) such that $1 \leq i \leq j \leq n$ and $\text{LCM}(a_i, a_{i+1}, \dots , a_j)$ $=$ $k \times \text{GCD}(a_i, a_{i+1}, \dots , a_j)$.

Input

The first line of the input contains an integer $t$ ($1 \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 $n$ and $k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 100$) $-$ the size of Efa’s array and her favorite number.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 100$).

Subtask 1 (10 Points): Sum of $n$ over all test cases doesn’t exceed $100$.

Subtask 2 (20 Points): Sum of $n$ over all test cases doesn’t exceed $1000$.

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

Output

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

Sample

Input	Output
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