Nasser's Array Reduction

Input

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

The first line of each test case contains a single integer $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6) — the length of the array.

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(1 \leq a_{1}, a_{2}, \dots, a_{n} \leq 1 0^{9})$ (1 \le a_1,a_2,\ldots,a_n \le 10^9) — the elements of the array.

It is guaranteed that the sum of all $n$ over all test cases does not exceed $1 0^{6}$ 10^6.

Output

For each test case, output a single integer — the minimum possible size of the array after performing at most two operations.

Examples

Example 1

Loading

Note

In the second test case, $n = 6$ n=6, $a = [1, 2, 2, 1, 5, 5]$ a=[1,2,2,1,5,5]

Operation $1$ : Delete $[2, 2]$ (positions $2, 3$ )
Array becomes $[1, 1, 5, 5]$ [1,1,5,5]
Operation $2$ : Delete $[1, 1]$ (positions $1, 2$ )
Array becomes $[5, 5]$
Final size: $2$

Scoring

Subtask $1$ ( $10$ points) : $(1 \leq \sum n \leq 10)$ (1 \le \sum n \le 10)
Subtask $2$ ( $15$ points) : $(1 \leq \sum n \leq 50)$ (1 \le \sum n \le 50)
Subtask $3$ ( $25$ points) : $(1 \leq \sum n \leq 3000)$ (1 \le \sum n \le 3000)
Subtask $4$ ( $100$ points) : No additional constraints.