Rahul returned to the Kumban town and found that the Mr Durgeshwar was busy in solving the problem and even Thangabali couldn't solved it yet.

It was festival time in the town, and all families were celebrating. There were very large families consisting of two parents as well as N (1< = N < = 10^9) children. The parents have decided to give their children a special treat this year which is crackers ! After all, it is a well-known fact that children love crackers.

With such a big family, the parents cannot afford that many crackers. As such, they wish to minimize how many they give out, but still ensure that each child gets at least a bit. The parents can only give out entire crackers, which can then be divided and passed around.

With this many children, not all of them know one another all that well. The children have names, of course, but their parents sought help from Durgeshwara, so they have also conveniently numbered them from 1 to N. There are M (1 <= M <= 10^5) unique two-way friendships among the children, where relationship i is described by the distinct integers Ai and Bi (1 <= Ai, Bi <= N), indicating that children Ai is friends with children Bi, and vice versa.

When a child is given a cracker, he can split it into as many pieces as he wants. He can then pass these pieces around to his friends, who can repeat this process themselves. Help Rahul to solve the problem so that he could defeat ThangaBali and the story ends happily !!

Input Specification:

First line contains an integer T that represents the number of test cases. Then follows two lines for each test case:
Line 1: 2 integers, N and M
Next M lines: 2 integers, Ai and Bi, for i=1..M

Output Specification:

For each test case, print A single integer, the minimum number crackers must be given out, such that each children ends up with at least a small part of a cracker.

Sample input:

1
4 3

1 2

2 3

3 4

Sample Output:

1