puzzle

Time Limit: 1000MS

Memory Limit: 65536KB

Description

小明在玩一个闯关游戏,共n关,必须按顺序通过,每一关会遇到两个数字(可能一样),他要选择其中一个,如果要选的这个数字是他之前选过的就直接过了这关。 但是他如果在某一关选了数字X,那就不能在经过另一关时选择数字Y当X+Y=2*n-1时,如果在某一关没有数可选的时候游戏结束问在闯关游戏中小明最多可以通过几关。

Input

第一行输入一个整数T(1 <= T <= 100),表示接下来T组测试数据, 每组测试数据第一行一个整数n(900<=n<=1000) 接下来n行每行两个整数a,b代表每关遇到的数字(0<=a,b<=2*n-1)

Output

每组测试数据输出一个整数,小明最多的过关数。

Sample Input

2
3
0 0
1 1
2 2
3
0 0
1 1
5 5

Sample Output

3
2

Hint

None

Source

None

提交代码