Description

Xiao Y is an OIer who loves traveling. One day, she arrives in a new city. Since she is not familiar with the transportation system there, she chooses to take the subway.

She discovers that each subway line can be regarded as a curve on the plane, and every intersection between different lines must have a transfer station. From her investigation, she learns that no line is a loop, and no line intersects itself. Any two distinct lines intersect only at finitely many points, have no overlapping segments, and no three lines pass through the same point. That is, the situations shown in the figure do not occur:

Xiao Y is riding subway line $0$, and along the way she passes $n$ transfer stations in order. She notes the line number available for transfer at each transfer station, and finds that every line shares at most $2$ transfer stations with the line she is on. Now Xiao Y wants to know, excluding the transfer stations she passed, what is the minimum possible number of other transfer stations in the city. Only if you give the correct answer will she agree to take you out next time.

Input Format

Please note that this problem contains multiple test cases.

The first line of the input data is an integer $T$, indicating the number of test cases. The test cases follow.

For each test case, the first line is an integer $n$, representing the number of transfer stations Xiao Y passed. The second line contains $n$ space-separated integers, in order, each indicating the line number available for transfer at that transfer station. These indices are all within $1\sim n$.

Output Format

For each test case, output a single integer on one line, representing the minimum number of transfer stations other than these $n$.

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

0 
0 
0 
1

Hint

[Explanation for Sample 1]

For the first two test cases in the sample, one possible optimal configuration is shown below.

[Subtasks]

There are $50$ test points, each worth $2$ points. You can only get full points for a test point if your answer is completely correct; otherwise, you get no points.

For all test points and for the samples, $1 \leq T \leq 100$, $1 \leq n \leq 44$. For each test point, the range of $n$ is given in the following table:

Translated by ChatGPT 5