Migrated from Lutece 2809 为啥清水河没有地铁

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

“为啥清水河没有地铁？”，瓜皮大哥经常因为要前往红高路或者犀浦才能乘坐地铁发出如此怒号。

现在给你一个成都市的地铁局部图，每条地铁线路可以看成平面上的一条曲线，不同线路的交点处一定会设有换乘站 。通过调查得知，没有线路是环线，也没有线路与自身相交。任意两条不同的线路只会在若干个点上相交，没有重合的部分，且没有三线共点的情况。

下图所示的情况都是不会存在的：

现在瓜皮大哥坐着 $x$ 号线，路上依次经过了 $n$ 个换乘站。他记下了每个换乘站可以换乘的线路编号，发现每条线路与她所乘坐的线路最多只有 $2$ 个换乘站。现在瓜皮大哥想知道，除掉经过的换乘站以外，这个城市里最少有几个换乘站。

Input

请注意本题有多组输入数据。

输入数据的第一行是一个整数 $T$，表示输入数据的组数。接下来依次给出每组数据。

对于每组数据，第一行是一个整数 $n$，表示瓜皮大哥经过的换乘站的数目。

第二行为 $n$ 个用空格隔开的整数，依次表示每个换乘站的可以换乘的线路编号。这些编号都在 $1$ 到 $n$ 之内。

Output

对于每组输入数据，输出一行一个整数，表示除掉这 $n$ 个换乘站之外，最少有几个换乘站。

Samples

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

Constraints

$1≤T≤100,1≤n≤44$

Note

这是样例前两个数据的可能解

Resources

2022 UESTC ICPC Training for String and Search Algorithm