**Problem**

**Input**

The first line is the number of test cases. For each test case, in the first line there is one integer n, 3 <= n <= 1000, which equals the number of points; in the second line there is one integer m, 0 <= m <= 250000, which equals the number of red segments; then the following m lines there are two integers p and k separated by a single space, 1 <= p, k <= n, they are vertices which are ends of a red segment.

**Output**

For each test case ,print the correct solution in a single line.

**Sample Input**

1

6

9

1 2

2 3

2 5

1 4

1 6

3 4

4 5

5 6

3 6

**Sample Output**

2