题目描述

给定一个长度为$n$的正整数序列$a_1, ... , a_n$.

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

接下来的操作将在新序列上进行.

求若干次操作后, 最终序列的长度最小的是多少.

输入格式

第一行一个正整数$T$, 表示数据组数.

对于每组数据

第一行输入一个正整数$n$, 表示序列的长度.

接下来一行输入$n$个正整数, 分别表示$a_1, ... , a_n$.

输出格式

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

数据范围

对于所有数据, 满足$1 \leq T \leq 10^3$, $3 \leq n$, $\sum{n} \leq 3 \cdot 10^5$, $1 \leq a_i \leq 10^9$.

样例输入

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

样例输出

2
4
2

题目来源

题目与数据均来自 Public Round #1 http://pjudge.ac/contest/883.

原题为International Zhautykov Olympiad 2022, Computer Science, Day 1, Problem 1.