众所周知，围棋是一项黑白双方轮流行动的棋类游戏。在围棋中，还有打劫的概念，若一方落子在某一个劫争处，则另一方不能立刻也下在这个劫争处，而之后还是可以下的。现在，你是一场史诗级围棋对弈（史诗级体现在这场棋每一步都下在了劫争上）的记谱员，但熬夜到早上七点才睡的你状态不佳，胡乱记了许多东西。 为了假装你有出色的完成记谱工作，请从你记录的谱子中找到一个最长的合法行棋子序列。 一个合法行棋子序列需要满足： 1. 任意相邻的两步，玩家不同（一黑一白）； 2. 任意相邻的两步，不能下在同一个劫争处。 子序列是指原序列中删除若干（可以不删）元素得到的新序列。

输入描述:

第一行是整数，测试组数。每组测试用例，第一行是整数，你记录的谱子长度。接下来行，每行两个数和，表示一步棋，下这步棋的人是且下在了编号为的劫争处。

输出描述:

每个测试用例输出一个整数，表示最长的合法行棋子序列长度。