题目描述
小 Y 是一个爱好旅行的 OIer。一天,她来到了一个新的城市。由于不熟悉那里的交通系统,她选择了坐地铁。
她发现每条地铁线路可以看成平面上的一条曲线,不同线路的交点处一定会设有换乘站 。通过调查得知,没有线路是环线,也没有线路与自身相交。任意两条不同的线路只会在若干个点上相交,没有重合的部分,且没有三线共点的情况。即,如图所示的情况都是不存在的:

小 Y 坐着地铁 0 号线,路上依次经过了 n 个换乘站。她记下了每个换乘站可以换乘的线路编号,发现每条线路与她所乘坐的线路最多只有 2 个换乘站。现在小 Y 想知道,除掉她经过的换乘站以外,这个城市里最少有几个换乘站。只有你告诉她正确的答案,她才会答应下次带你去玩呢。
输入格式
请注意本题有多组输入数据。
输入数据的第一行是一个整数 T,表示输入数据的组数。接下来依次给出每组数据。
对于每组数据,第一行是一个整数 n,表示小 Y 经过的换乘站的数目。第二行为 n 个用空格隔开的整数,依次表示每个换乘站的可以换乘的线路编号。这些编号都在 1∼n 之内。
输出格式
对于每组输入数据,输出一行一个整数,表示除掉这 n 个换乘站之外,最少有几个换乘站。
对于样例的前两组数据,一种可能的最优答案如下图所示。
提示
一共有 50 个测试点,每个测试点 2 分。你只有在答案完全正确时才能得到该测试点的全部分数,否则不得分。
对于所有测试点,以及对于样例, 1≤T≤100, 1≤n≤44。对于每个测试点, n 的范围如下表:
测试点编号 |
1≤n≤ |
测试点编号 |
1≤n≤ |
1 |
2 |
19 |
26 |
2 |
3 |
20 |
28 |
3 |
4 |
21∼22 |
30 |
4 |
5 |
23∼24 |
31 |
5 |
6 |
25∼26 |
32 |
6 |
8 |
27∼28 |
33 |
7 |
9 |
29∼30 |
34 |
8 |
10 |
31∼32 |
35 |
9 |
11 |
33∼34 |
36 |
10 |
12 |
35∼36 |
37 |
11 |
13 |
37∼38 |
38 |
12 |
14 |
39∼40 |
39 |
13 |
15 |
41∼42 |
40 |
14 |
16 |
43∼44 |
41 |
15 |
17 |
45∼46 |
42 |
16 |
20 |
47∼48 |
43 |
17 |
22 |
49∼50 |
44 |
18 |
24 |
|