[AdditionalFile5531.zip](file://AdditionalFile5531.zip?type=additional_file)

#5531. 「PA 2018 Final」Na kawałeczki

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2018 Final Na kawałeczki

有些孩子梦想得到自行车、电动火车或娃娃屋。然而，Bituś 在给圣诞老人的信中许下了一个完全不同的愿望。他的愿望实现了！小男孩在圣诞树下收到了一个彩色模型切割套装：剪刀、一张矩形纸（也称为卡片）和一组蜡笔。孩子们不认识像「李子色」或「紫红色」这样奇怪的颜色名称，所以蜡笔的颜色用连续的自然数编号。

Bituś 将矩形的四个边按顺时针方向分别涂成颜色 $1$、$2$、$3$、$4$。然后，他将初始矩形切割成 $N+1$ 个较小的块。整个操作包括 $N$ 个步骤。每个步骤包括取出一块碎片，用蜡笔画一条连接两个边中点的线段，然后沿画线切割该碎片。第 $i$ 个步骤使用的蜡笔颜色为 $i+4$，因此切割后得到的两块较小碎片各有一个颜色为 $i+4$ 的边。（可以证明，所有碎片都是凸形图形，因此每次切割确实会产生恰好两块较小碎片。）

Bituś 记录了连接边的颜色：在第 $i$ 个步骤中，他用线段连接了颜色为 $a_{i}$ 和 $b_{i}$ 的边。然而，你怀疑 Bituś 在某个时刻可能犯了错误。对于给定的步骤序列 $(a_{i}, b_{i})$，找到该序列的最长前缀长度，即 Bituś 可能执行的正确步骤（切割）序列。

Bituś 讨厌重复，因此每个无序对 $(a_{i}, b_{i})$ 最多出现一次。

输入格式

输入的第一行包含一个整数 $T$ $(1 \leq T \leq 5)$，表示输入中的测试用例数量。

每个测试用例描述的第一行包含一个整数 $N$ $(1 \leq N \leq 200)$，表示执行的步骤数量。

接下来的 $N$ 行描述步骤：第 $i$ 行包含两个不同的整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq i+3)$，表示第 $i$ 个步骤的描述。在同一个测试用例中，无序对是不同的，即对于 $i \neq j$，不会出现 $(a_{i}=a_{j}$ 且 $b_{i}=b_{j})$ 或 $(a_{i}=b_{j}$ 且 $a_{j}=b_{i})$ 的情况。

输出格式

在第 $i$ 行输出一个整数，表示第 $i$ 个测试用例中步骤序列的最长正确前缀长度。

样例

输入

2
4
3 1
1 5
4 6
2 4
5
3 4
1 2
5 6
1 5
8 7

输出

3
5

下图展示了如何为第一个测试用例获得长度为 $3$ 的正确前缀。执行第四个步骤是不可能的，因为没有一块碎片同时包含颜色为 $2$ 和 $4$ 的边。请注意，如果在第二个步骤中对右侧碎片执行 $1-5$ 的切割，则无法执行第三个步骤的切割。