Triple — Eolymp

Input

The first line contains the number of test cases $t$ ( $1$ $\leq$ $t$ $\leq$ $1 0^{4}$ 10^4). The description of the test cases follows.

The first line of each test case contains one integer $n$ ( $3$ $\leq$ $n$ $\leq$ $2 \cdot 1 0^{5}$ 2 \cdot 10^5) — the size of the array $a$ .

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

It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Output

For each test case, output a single integer — the minimum number of elements that need to be replaced in the first stage so that it is possible to obtain an array of the form $[x, x, x]$ [x, x, x] for some integer $x$ .

Examples

Example 1

Loading

Example 2

Loading

Example 3

Loading

Note

For the first test case, the answer is $0$ since we can apply the first type of operation to the segment $[1, 2]$ and obtain the array $[3, 3, 3]$ [3,3,3].

For the second test case, the answer is $1$ since we can apply the second type of operation once for $i = 4$ i = 4 and make $a_{4} = 3$ a_4 = 3. After that, we will apply the first type of operation to the segment $[1, 2]$ and obtain the array $[3, 3, 3]$ [3,3,3].

For the third test case, the answer is $2$ since we can apply the second type of operation twice. The first time for $i = 1$ i = 1 and the second time for $i = 2$ i = 2.

Scoring

Subtask $1$ ( $30$ points) : $(a_{i} \leq 10)$ (a_i \le 10)
Subtask $2$ ( $50$ points) : $(n \leq 2 \cdot 1 0^{3})$ (n \le 2 \cdot 10^3)
Subtask $3$ ( $70$ points) : No additional constraints