说明

朱达远同学小的时候是个路痴，他曾经创下了沿着一个环形道路走了三天三夜没有走出去的记录。虽说最后警察叔叔把他带回家了，但是这个童年的阴影一直伴随着他。现在朱达远同学终于长大了，并且成为了某个国家的道路规划师。这个国家目前还没有一条道路能够连通两座城市。由于对环形道路的恐惧，他决定阻止一些道路的施工，让任意两个城市之间要么没有路可以到达，要么只能有一条路可以到达。但是如果朱达远同学阻止了过多道路的建设，他的这个邪恶的计划就会被人发现。最少要阻止多少道路的施工呢？朱达远同学觉得十根手指算不过来，于是他就来找到了聪明的你，让你来帮他计算一下。

输入格式

输入第一行为一个整数T，表示有T组数据。每组数据第一个行包括一个整数n（0<n<=10000），表示有n条路即将被建设。接下来n行，每行两个整数，A和B，表示准备在A城市和B城市之间建设一条道路（0<=A,B<=10000）。

输出格式

每组数据输出一行，每行一个数字，表示至少需要阻止的道路数量。

样例

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

1
3

提示

1