Problem Description

Alice has an array $a$. The array has $N$ positive numbers. She thinks the array is too long, so she wants to shorten the array. She decides to shorten the array via the following operation: every time she will choose an index $i$ $(1 \le i<n)$ which $a_i > 0$ and $a_{i+1} > 0$. She will delete $a_i$ and $a_{i+1}$ and use $(a_i\operatorname{mod} a_{i+1})$ or $(a_{i+1}\operatorname{mod} a_{i})$ to replace them.

For example, for array $[3, 2, 4, 5]$, if Alice choose $i=2$, she can change the array to $[3, 2, 5]$ or $[3, 0, 5]$. Alice wants you to tell her the shortest possible length of the array after several options.

Input

The first line contains a single integer $T$ $(1 \le T \le 10)$, indicating the number of test cases.

For each test cases:

The first line contains one integer $N$ $(2 \le N \le 10^6)$, indicating the size of the array.

The next line contains $N$ integers $a_i$ $(a_i \le 10^{9})$, representing the array.

Output

Output $T$ lines.

The $i$-th line contains a single integer, representing the answer of $i$-th test case.

2
4
1 1 1 1
4
2 3 4 5

2
1

Hint

For the first sample, Alice first choose $i=1$ to change the array to $[0, 1, 1]$, then choose $i=2$ to change the array to $[0, 0]$, which is the best result she can reach.