Given a sequence of $n$ positive integers $a_1, \dots, a_n$.

You can perform several operations. In each operation, you can choose an index $i \in [2, n-1]$ such that $a_i = \frac{a_{i-1} + a_{i+1}}{2}$, then remove $a_i$ from the sequence, and shift the subsequent elements forward to fill the gap.

Find the minimum possible length of the sequence after performing any number of operations.

Input

The first line contains a positive integer $T$, representing the number of test cases. For each test case:

• The first line contains a positive integer $n$;
• The second line contains $n$ positive integers $a_1, \dots, a_n$.

Output

For each test case, output a single line containing a positive integer representing the answer.

Examples

Input 1

3
5
1 2 3 4 5
7
1 3 5 6 7 8 10
3
1 1 1

Output 1

2
4
2

Note

For the first test case $[1, 2, 3, 4, 5]$, you can remove $2, 4, 3$ in sequence.

For the second test case $[1, 3, 5, 6, 7, 8, 10]$, you can remove $3, 7, 8$ in sequence.

For the third test case $[1, 1, 1]$, you can remove the middle $1$.

Input 2

(input data)

Output 2

(output data)

Constraints

For all data, $n \ge 3$, $1 \le T \le 10^3$, $\sum n \le 3 \cdot 10^5$, $1 \le a_i \le 10^9$.