3305：Surveillance

See.Eye.A, the world's biggest independent intelligence agency, is located in a very large underground building. Recently, due to the large amount of secret documents kept in different departments and due to some recent strange activities in the building, the managers of See.Eye.A have decided to install an advanced surveillance system to monitor all the activities within the building. But lack of budgets has forced them to accomplish this task with the minimum expenses possible.

To be more specific, the building is consisted of a set of long passages containing doors at their two ends. If two passages i and j share the same door, then one can enter passage i from j or exit from passage i to j through that door. It should be noted that there is exactly one simple path through passages and other doors between each pair of doors (i.e. the structure of the passages and the doors is like a tree). Also note that the doors are made circular and as a result, more than 2 passages can share the same door. In addition, to extend the building in future, a door may be a dead-end i.e. a door that does not connect its passage to another one.

Now, they want to know the minimum number of cameras that can be installed to monitor all the doors and passages of the building, and they hired you to write a program to accomplish this task for them.

The first line of input contains a single integer T, which is the number of test cases. Each test case starts with a line containing one integer 1 ≤ P ≤ 100 which is the number of passages in the building, followed by P lines each containing a pair of integers 0 ≤ A, B ≤ 1,000,000,000 which are the unique IDs of the two doors at either side of each passage.

For each test-case, your program should output the minimum number of needed cameras to monitor all the building, in a single line.