Let's call an array **good**, if for any with .

You are given a **good** array of positive integers .

You can perform the following operations on this array:

- Choose any index () and a number (). Then, set to . After this operation, the array has to remain
**good**.

You want to perform several operations so that the resulting array will contain exactly two distinct values. Determine the smallest number of operations needed to achieve this goal.

#### Input Format

The first line of input contains the integer (), the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer () - the length of the array.

The second line of each test case contains integers () - elements of the array. It's guaranteed that for (that is, the array is **good**).

It is guaranteed that the sum of over all test cases does not exceed .

#### Output Format

For each test case, output a single integer - the smallest number of operations needed to achieve an array in which there are exactly two distinct values.

#### Constraints

Subtask | Points | Additional constraints |
---|---|---|

The sum of over all test cases does not exceed | ||

The sum of over all test cases does not exceed | ||

The sum of over all test cases does not exceed | ||

No additional constraints. |

#### Sample Input

```
2
5
4 5 2 4 5
2
1 2
```

#### Sample Output

```
3
0
```

#### Explanation

In the first test case, one of the optimal sequences of operations is:

`(4, 5, 2, 4, 5) → (2, 5, 2, 4, 5) → (2, 5, 2, 4, 2) → (2, 5, 2, 5, 2).`

In the second test case, the array already contains only two distinct values, so the answer is .

## Comments