Chef has an array A of length N.

An index i is called strong if we can change the [gcd] of the whole array just by changing the value of A_{i}.

Determine the number of strong indices in the array.

------ Input Format ------

• First line will contain T, number of test cases. Then the test cases follow.
• First line of each test case contains an integer N denoting the size of the array A.
• Second line contains $N space separated integers A_{1}, A_{2}, \dots, A_{N} -$ denoting the array A.

------ Output Format ------

For each test case, output the number of strong indices in the array.

------ Constraints ------

$1 ≤ T ≤ 5 \cdot 10^{4}$
$2 ≤ N ≤ 3 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases do not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------
3
3
5 10 20
4
3 5 7 11
4
2 2 2 2

----- Sample Output 1 ------
3
0
4

----- explanation 1 ------
Test Case $1$: All the indices are strong.
- For index $1$ you can change the element to $10$ which changes the gcd of the array to $10$.
- For index $2$ you can change the element to $12$ which changes the gcd of the array to $1$.
- For index $3$ you can change the element to $12$ which changes the gcd of the array to $1$.

Test Case $2$: No index is strong. If you change any single element, gcd still remains the same.

Test Case $3$: All the indices are strong. You can change any element to $3$. This changes the gcd of the array to $1$.

见题面

见题面