Nancy loves talking to people! When she is not busy holding classes for DCE Coders, she really enjoys chatting with her friends on social networking sites. One day, she realised that apart from her huge network of friends, she is also indirectly connected to a lot of people on these sites, such as friends of her friends, their friends and so on.

Formally, 2 people, A and B are said to be connected if:

1. They are friends OR
2. There is at least 1 person who is connected to both A and B.

Now, Nancy wants to know what is the minimum number of people she needs to add as friends, so that she is connected to all the students from DCE. Since you all are her favourite students, she asks for your help. Can you help her out?

Input

The first line contains T, the number of test cases.

The first line of each test case contains 2 integers, N and M. N is the total number of students in the college. Each student is identified by a unique index from 1 to N.

This is followed by M lines. Each line consists of 2 distinct integers, S1 and S2 indicating that S1 is a friend of S2 and vice versa. S1 and S2 lie between 1 and N (inclusive).

You can assume that Nancy always has index 1.

Output

For each test case, output a single line containing the minimum number of friends Nancy needs to add.

Constraints

1 <= T <= 10

1 <= N <= 100000

0 <= M <= min(100000, N * (N-1)/2)

Example

Input:
2
3 1
1 2
6 2
1 2
3 5

Output:
1
3