题号：NC227311
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
众所周知，围棋是一项黑白双方轮流行动的棋类游戏。在围棋中，还有打劫的概念，若一方落子在某一个劫争处，则另一方不能立刻也下在这个劫争处，而之后还是可以下的。现在，你是一场史诗级围棋对弈（史诗级体现在这场棋每一步都下在了劫争上）的记谱员，但熬夜到早上七点才睡的你状态不佳，胡乱记了许多东西。
为了假装你有出色的完成记谱工作，请从你记录的谱子中找到一个最长的合法行棋子序列。
一个合法行棋子序列需要满足：
1. 任意相邻的两步，玩家不同（一黑一白）；
2. 任意相邻的两步，不能下在同一个劫争处。
子序列是指原序列中删除若干（可以不删）元素得到的新序列。
为了假装你有出色的完成记谱工作，请从你记录的谱子中找到一个最长的合法行棋子序列。
一个合法行棋子序列需要满足：
1. 任意相邻的两步，玩家不同（一黑一白）；
2. 任意相邻的两步，不能下在同一个劫争处。
子序列是指原序列中删除若干（可以不删）元素得到的新序列。
输入描述:
第一行是整数，测试组数。
每组测试用例，第一行是整数，你记录的谱子长度。
接下来行，每行两个数
和
，表示一步棋，下这步棋的人是
且下在了编号为
的劫争处。
输出描述:
每个测试用例输出一个整数，表示最长的合法行棋子序列长度。