有些孩子梦想着自行车、电动火车或玩偶屋。然而，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 \le T \le 5$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $N$ ($1 \le N \le 200$)，表示执行的步骤数。接下来的 $N$ 行包含步骤描述：其中第 $i$ 行包含两个不同的整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le i + 3$)，表示第 $i$ 步的描述。在同一个测试用例中，给定的无序对各不相同，即对于 $i \neq j$，不存在 $(a_i = a_j \text{ 且 } b_i = b_j)$ 或 $(a_i = b_j \text{ 且 } a_j = b_i)$ 的情况。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示给定步骤序列中最长合法前缀的长度。

样例

样例输入 1

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

样例输出 1

3
5

说明

样例说明：下图展示了如何为第一个测试用例获得长度为 3 的合法前缀。执行第四步是不可能的，因为没有包含颜色 2 和 4 的边的碎片。请注意，如果在第二步中，1–5 的切割是在右侧碎片上进行的，那么第三步的切割将无法执行。