INC Pradnya team wants to publicize their event so as to get maximum participants. Hence the official INC Pradnya'15 head decides to send messages to students in Pune. However he has very little balance left on his phone. He cannot invite everybody. He can send only K messages.
A student receiving the message forwards it to all his friends. A person participates in the event only if he or she receives at least one message. Our Pradnya'15 head knows who is friends with whom. Using this knowledge he wants to reach out to maximum number of students.
Output the maximum students he can reach out to, on a single line

 

 

Input

 

• The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains three space separated integers N, M and K where N denotes the total number of students in Pune, M denotes the number of pairs of students who are friends and K denotes the number of messages that can be sent.
• The next M lines contains 2 space-separated integers denoting a pair of friends.

 

Output

 

• For each test case, output a single line containing the maximum students he can reach out to.

 

 

Constraints

 

• 1 = T = 1000
• 1 = N = 100000
• 1 = M = 100000
• 0 = K = 1000000

 

 

Example

Input: 1 3 2 2 1 2 2 3 Output: 3