给定一个包含 $n$ 个正整数的数组 $a$。在一次操作中，如果一个数等于其相邻两个数的算术平均值，你可以将其从数组 $a$ 中移除。但是，你不能移除数组的第一个和最后一个数。形式化地，如果 $a_i = \frac{a_{i-1} + a_{i+1}}{2}$，你可以移除 $a_i$。例如，如果你从数组 $[1, 3, 6, 9, 4]$ 中移除 $6$，得到的数组将是 $[1, 3, 9, 4]$。
请问通过进行若干次（可能为零次）上述操作，你能得到的数组的最短长度是多少？
输入格式
第一行包含一个整数 $t$ ($1 \le t \le 10^3$) —— 测试用例的数量。
接下来的 $2 \cdot t$ 行遵循以下格式： 每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 3 \cdot 10^5$) —— 数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$，对于每个 $i$，其中 $1 \le i \le n$)。
保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。
输出格式
对于每个测试用例，输出一个整数 —— 通过使用上述操作所能得到的数组的最短长度。
子任务
令 $S$ 为所有测试用例中 $n$ 的总和。
| 子任务 | 附加约束 | 分值 | 必要子任务 |
|---|---|---|---|
| 0 | 样例 | 0 | — |
| 1 | $n \le 15, S \le 400$ | 14 | 0 |
| 2 | $a_i = i$ | 13 | — |
| 3 | $a_i \le 3$ | 9 | — |
| 4 | $n \le 300, S \le 1000$ | 17 | 1 |
| 5 | $n \le 3000, S \le 10000$ | 18 | 4 |
| 6 | — | 29 | 2, 3, 5 |
样例
输入 1
3 5 1 2 3 4 5 7 1 3 5 6 7 8 10 3 1 1 1
输出 1
2 4 2
说明
例如，在数组 $[1, 2, 4]$ 中，没有任何可行的操作，因为 $\frac{1+4}{2} = 2.5 \neq 2$。