There are n points given in a space. There are no three points, such that they lie on the same straight line. Each pair of points is connected by a segment coloured red or black. Each triangle, whose sides have the same colour is called a monochromatic triangle. We are given a list of all red segments and we want to find the number of all monochromatic triangles.


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.


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

Sample Input

1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6

Sample Output