Lucky Cities

John has recently arrived in Romania for the South Eastern European Regional competition. Since John has never been to Romania before, the hosts decided to organize a sightseeing tour for him. Such a tour includes several Romanian cities, and none of them is visited more than once. John starts in one city, visits some other cities according to a guided route, and at the end of the tour returns 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. A sightseeing tour for John is a sequence of cities $c_1, c_2, \dots, c_n$ such that all $c_i$ are distinct, $c_i$ and $c_{i+1}$ are connected by a road for $i = 1, 2, \dots, n-1$, and $c_n$ and $c_1$ are connected by a road as well.

Being an odd person, John would like to visit an odd number of cities. The organizers have drawn the plans of all possible tours with an odd number of cities, and only such tours are considered.

The residents of a city would love John to visit them. A city is called lucky if there is at least one such tour (with an odd number of cities) passing through it. Your task is to compute the number of lucky cities in Romania.

The first line of input contains a single integer $T$ — the 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 contains two integers $a_i$ and $b_i$ separated by a single space — the labels of the cities that the $i$-th road connects.

The output should contain $T$ lines — the answer for each of the test cases, in order.

• $1 \le T \le 77$
• $0 \le N, M \le 10^5$
• $1 \le a_i < b_i \le N$