给定一个长为 $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$ 。
| 测试点编号 | $n\le$ | $\sum n\le$ | 特殊性质 |
|---|---|---|---|
| $1\sim 3$ | $15$ | $400$ | $ $ |
| $4\sim 6$ | $a_i=i$ | ||
| $7\sim 8$ | $a_i\le 3$ | ||
| $9\sim 12$ | $300$ | $10^3$ | |
| $13\sim 16$ | $3\cdot 10^3$ | $10^4$ | |
| $17\sim 20$ | $ $ | $ $ |
时间限制：$\texttt{1s}$
空间限制：$\texttt{512MB}$