You are given an array $$$a$$$ of length $$$n$$$ consisting of positive integers.
An index $$$i$$$ $$$(1 \le i \lt n)$$$ splits the array into two non empty subarrays: $$$[a_1, a_2, \dots, a_i]$$$ and $$$[a_{i+1}, a_{i+2}, \dots, a_n]$$$.
We call an index $$$i$$$ good if it is possible to make
$$$$$$ \gcd(a_1, a_2, \dots, a_i) = \gcd(a_{i+1}, a_{i+2}, \dots, a_n) $$$$$$
by changing the value of at most one element in the array to any positive integer.
Note that the modification (if any) can be applied to any position in the array and is considered independently for each index.
Your task is to determine the number of good indices.
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ — the number of test cases.
Each test case consists of two lines.
The first line contains a single integer $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — the length of the array.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the number of good indices.
2612 6 18 3 9 1584 8 16 2 10 5 20 25
5 5
For the second test case,
| $$$i$$$ | Left Array | Right Array | GCD (Left, Right) | Good? |
| 1 | [1] | [8,16,2,10,5,20,25] | (1, 1) | Yes |
| 2 | [1,8] | [16,2,10,5,20,25] | (1, 1) | Yes |
| 3 | [1,8,16] | [2,10,5,20,25] | (1, 1) | Yes |
| 4 | [4,8,16,2] | [10,5,20,25] | (2, 5) | No |
| 5 | [4,8,16,2,10] | [5,20,25] | (2, 5) | No |
| 6 | [4,8,16,2,10,5] | [1,25] | (1, 1) | Yes |
| 7 | [4,8,16,2,10,5,20] | [1] | (1, 1) | Yes |
The bold entries in the table represent the numbers that were modified from their original values.
Thus, indices $$${1, 2, 3, 6, 7}$$$ are good.
| Insomnia-26 |
|---|
| Finished |
