给定一个长为 $n$ 的正整数序列 $a_1,\cdots,a_n$。

你可以进行若干次操作，每次操作你可以选择一个位置 $i\in[2,n-1]$ 使得 $a_i=\dfrac{a_{i-1}+a_{i+1}}{2}$，随后将 $a_i$ 删去，之后的数按顺序向前补空位。

求若干次操作后序列长度最小可以是多少。

输入格式

第一行，一个正整数 $T$，表示数据组数。之后对于每组数据：

• 第一行，一个正整数 $n$；
• 第二行，$n$ 个正整数 $a_1,\cdots,a_n$。

输出格式

对于每组数据，输出一行，一个正整数，表示答案。

样例一

input

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

output

2
4
2

explanation

对于第一组数据 $[1,2,3,4,5]$，依次删除 $2,4,3$ 即可。

对于第二组数据 $[1,3,5,6,7,8,10]$，依次删除 $3,7,8$ 即可。

对于第三组数据 $[1,1,1]$，删除中间的 $1$ 即可。

样例二

见下发文件，该样例符合测试点 $17\sim 20$ 的限制。

数据范围

本题共 $20$ 组测试点，各 $5$ 分。

对于所有数据，$n\ge 3$，$1 \le T\le 10^3$，$\sum n\le 3\cdot 10^5$，$1 \le a_i\le 10^9$ 。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$