O. Optimal GCD Split
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

For each test case, output a single integer — the number of good indices.

Example
Input
2
6
12 6 18 3 9 15
8
4 8 16 2 10 5 20 25
Output
5
5
Note

For the second test case,

$$$i$$$Left ArrayRight ArrayGCD (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.