B. Jebreel hates Moon's Game (Fushi)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jebreel and Moon are playing a game on a graph with $$$n$$$ nodes and $$$m$$$ edges.

The Rules of the Game:

  1. Jebreel goes first. He chooses any uncolored node and colors it grey.;
  2. Moon then chooses a different uncolored node and colors it black.

They take turns until $$$5$$$ nodes total have been colored.

Jebreel wins if he manages to color a path of length $$$2$$$, meaning $$$3$$$ connected grey nodes. Otherwise, Moon wins.

Assuming both players play optimally, how many different starting nodes exist that guarantee a win for Jebreel?

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — denotes the number of test cases.

The first line of each test case contain two integers $$$n$$$ $$$(3 \le n\le 10^5)$$$, and $$$m$$$ $$$(0\le m\le \min\left(\frac{n(n-1)}{2},2\cdot 10^5\right)$$$ — denotes the number of nodes and edges in the graph respectively.

Then $$$m$$$ lines follow, the $$$i_{th}$$$ line contains two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \le u_i , v_i \le n)$$$ — denotes the two nodes that the $$$i_{th}$$$ edge connects.

It is guaranteed that there are no self-loops or multiple-edges in the given graph.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print how many different starting nodes exist that guarantee a win for Jebreel?

Example
Input
1
8 9
1 2
1 4
1 5
2 3
2 7
3 4
3 5
3 6
4 6
Output
5