John has recently arrived in Romania for the South Eastern European Regional competitions. John has never been to Romania before so Romanians decided to organize sightseeing tour for him. This tour will include several Romanian cities and none of them will be visited more than once. John will start in one city and will visit some other cities according to a guide tour. At the end of the tour John will return to the starting point.

There are N cities numbered from 1 to N and M two-way roads in the country. Each road connects two different cities. Consider a sightseeing tour for John c₁, c₂, ..., c_n, where each c_i denotes a city in Romania. Then all c_i must be distinct, c_i and c_i+1 must be connected by a road, where i=1, 2, ..., n-1, c_n and c₁ must be connected by a road as well. 

Being a odd person John would like to visit an odd number of cities. The organizers have drawn the plan of all possible tours with an odd number of cities. 

Residents of the cities would like John to visit them. So if there is at least one tour passing through some city than this city is called lucky. Your task is to calculate the number of lucky cities in Romania.

Input

The first line of input contains a single integer T – a number of test cases. Every test case starts with a line containing two integers separated by a single space – N and M. Each of the next M lines will contain two integers a_i and b_i separated by a single space – the labels of cities that i-th road connects.

Output

Output should contain T lines – answers for each of the test cases.

Constraints

1 ≤ T ≤ 77,
0 ≤ N, M ≤ 100000 (10⁵),
1 ≤ a_i < b_i ≤ N

Example

Input:
1
7 7
1 5
3 5
3 7
1 7
6 7
4 7
4 6

Output:
3

PS: If you like this problem, also see problem BUSINESS