#1511. D

D

说明

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

输入格式

输入第一行为一个整数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