D. Awkward Middle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$.

You can perform the following operation any number of times, possibly zero:

Choose an index $$$i$$$ such that $$$1 \lt i \lt |a|$$$ and $$$a_{i-1} = a_{i+1}$$$, then remove the $$$i$$$-th element from the array.

Here, $$$|a|$$$ denotes the current length of the array.

Your task is to find the minimum possible length of the array after performing the operation any number of times.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum possible length of the array after performing the operation any number of times.

Example
Input
3
5
1 2 1 3 1
4
1 2 3 4
6
2 5 2 5 2 5
Output
2
4
3
Note

In the first test case, one possible sequence of operations is:

$$$$$$ [1, 2, 1, 3, 1] \rightarrow [1, 1, 3, 1] \rightarrow [1, 1, 1] \rightarrow [1, 1] $$$$$$

So the minimum possible length is $$$2$$$.

In the second test case, no operation can be performed, so the answer is $$$4$$$.

In the third test case, the array can be reduced to length $$$3$$$.