Time Limit: 3000 MS    Memory Limit: 65536 K 


Description

Give N points in the space,and any three of them aren't on the same line. Each pair of points are connected by a red or black line. If three edges of a triangle have the same color, then we call the triangle as a single color triangle. Can you tell me the number of single color triangles?

Input

The first line of the input will be a integer to represent the number of test cases. For each test case there M+1 lines. The first line contains two integers N and M. Then M lines each contains two integers ai and bi. Represent there is a red line between ai and bi. Each red line will given exact once. ( 1 <= N <= 1000000 , 0 <= M <= min(1000000,N*(N-1)/2) , 0 <= ai,bi < N) There is a blank line before each test case.

Output

For each test case output the answer on a single line: The number of single color triangles.

Sample Input

6 3 3 0 1 1 2 0 2 3 2 0 1 1 2 4 6 0 1 1 2 2 3 0 2 0 3 1 3 5 10 0 1 0 2 0 3 0 4 1 2 1 3 1 4 2 3 2 4 3 4 1000000 0 1000000 1 1 2

Sample Output

1 0 4 10 166666166667000000 166666166666000002

Source

wqb0039