Deleting Numbers

Problem Source

The problem and data are both from Public Round #1 (http://pjudge.ac/contest/883).

The original problem is International Zhautykov Olympiad 2022, Computer Science, Day 1, Problem 1.

Problem Description

You are given a sequence $a_1, \dots, a_n$ of $n$ positive integers.

You may perform the following operation any number of times: choose a position $i \in [2, n-1]$ such that $a_i = \frac{a_{i-1} + a_{i+1}}{2}$, delete $a_i$, and then shift the following numbers forward to fill the gap.

Subsequent operations are performed on the new sequence.

Find the minimum possible final length of the sequence after several operations.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains a positive integer $n$, the length of the sequence.

The next line contains $n$ positive integers $a_1, \dots, a_n$.

Output Format

For each test case, output one positive integer on a single line: the answer.

Sample Input

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

Sample Output

2
4
2

Constraints

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