Tom and Jerry are lifelong rivals. Tom rarely succeeds in catching Jerry, mainly because of Jerry's cleverness, cunning abilities, and luck.

There are N*N rooms in the form of an NxN matrix. There are doors connecting some adjacent pairs of rooms. The door makes it possible to move from one room to another. If there is a door connecting room A and B, one can move from room A to B and vice versa. All other sides are seperated by a solid wall.

You need to find the number of pairs of Tom-Jerry Positions such that Jerry is completely safe from Tom.

For example -

In the above image the safe pairs of Tom - Jerry Positions are -

1,1 - 2,1
1,2 - 2,1
2,2 - 2,1
2,1 - 1,1
2,1 - 1,2
2,1 - 2,2

Thus there are six safe position pairs.

CONSTRAINTS:-
1 ≤ T ≤ 10
1 ≤ N,G ≤ 20

INPUT FORMAT
First line consists of single integer T. T test cases follows

each test case begins with 2 integers - N and G. (G is the number of gates)
G lines follows - each line containing 4 integers x1 y1 x2 y2 - positions of 2 rooms connected by the ith gate.
for more clarity check example

OUTPUT FORMAT
T lines - ith line answer to ith test case