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