Given a acyclic graph with N nodes and E undirected edges and degree (number of edges incident on that node) of every node is < 3.

Find maximum number of edges that can be added to this graph such that there is no cycle of length <= 3.

Input

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains a 2 integers N and E denoting the number of nodes and number of edges.

Next E lines contains 2 integers a,b denoting that there is an edge between node a and b.

Output

For each test case, output a single line containing the required answer.

Constraints

1 <= T <= 100000

1 <= N <= 10^5

1 <= E <= 10^5

Sum of E over all testcases <= 1000000

Sample Input

1

3 1

1 2

Sample Output

1