All Submissions


Problem Statement

Due to some recent unfortunate events, BIT Mesra has become a battle ground for some fierce and deathly fighting between the ACM members and Non-ACM members. The Vice Chancellor wants to know who will survive finally. But he is too afraid to go to the fighting arena.

So, he made a plan. He collected the information from the DC main chat of the college. He found the information about all the dual fights. Dual fight means a fight between a ACM member and a Non-ACM member. He knows the name of the dual fighters, but doesn't know which one of them is an ACM member or not a member. He also read it on the chat that the number of ACM members is definitely less than the number of Non-ACM Members.

So, the VC listed all the rivals. He now wants you to find out the maximum possible number of Non-ACM members.

INPUT

Input starts with an integer T (<= 20), denoting the number of test cases.

Each case contains an integer n (1 <= n <= 105), denoting the number of dual fights. Each of the next n lines will contain two different integers u v (1 <= u, v <= 20000) denoting there was a fight between u and v. No rivalry will be reported more than once.

Output

For each case print the maximum possible number of Non-ACM members.

Sample Input


2
2
1 2
2 3
3
1 2
2 3
4 2


Sample Output


2
3


Problem Setter: Md Taha Bin Jawaid (TBJ)

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0