Little Y is an OIer who loves traveling. One day, she arrived in a new city. Unfamiliar with the local transportation system, she chose to take the subway.

She discovered that each subway line can be viewed as a curve on a plane, and transfer stations are always located at the intersections of different lines . Investigations revealed that no lines are circular, and no line intersects itself. Any two distinct lines intersect at only a finite number of points, have no overlapping segments, and no three lines intersect at the same point. That is, the situations shown in the figure below do not exist:

Little Y rode subway line $0$ and passed through $n$ transfer stations in sequence. She recorded the line number for each transfer station and found that each line has at most $2$ transfer stations with the line she was riding. Now, Little Y wants to know the minimum number of transfer stations in the city, excluding the ones she passed through. She will only agree to take you along on her next trip if you can tell her the correct answer.

Input

Read the data from standard input.

Please note that this problem contains multiple test cases.

The first line of the input contains an integer $T$, representing the number of test cases. Each test case follows.

For each test case, the first line contains an integer $n$, representing the number of transfer stations Little Y passed through. The second line contains $n$ space-separated integers, representing the line numbers available for transfer at each station in order. These numbers are between $1$ and $n$.

Output

Output to standard output.

For each test case, output a single integer on a new line, representing the minimum number of transfer stations in the city, excluding the $n$ stations she passed through.

Examples

Input 1

4
4
1 2 1 2
8
1 2 3 4 1 2 3 4
5
5 4 3 3 5
8
1 2 3 4 1 3 2 4

Output 1

0
0
0
1

Note

For the first two test cases, one possible optimal answer is shown in the figure below.

Constraints

There are 50 test cases in total, each worth 2 points. You will only receive full points for a test case if your answer is completely correct; otherwise, you will receive no points.

For all test cases, as well as the examples, $1 \le T \le 100$ and $1 \le n \le 44$. The range of $n$ for each test case is as follows: