There is a chessboard with n rows and n columns, every position is black or white. It is defined that c(x,y) means the color of the position in the xth row and the yth column, and it is guaranteed that c(x,y)=c(y,x)=c(x,n−y+1)=c(n−x+1,y) for any 1≤x,y≤n, which shows it is quite symmetry. Also because of this, only the colors of the positions (x,y) which satisfies x≤y≤⌊n+12⌋ are given, and the number of the given black position is t in total. Now HazelFan has a big cube with n layers and n rows and n lines, and its six sides are all same as the chessboard. For the three pairs of opposite sides, for each black position on one side, he will dig through the cube from the position straight to a black position on the other side. Please tell him after he destroys the cube, how many little cubes are left.

The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
For each test case:
The first line contains two positive integers n,t(1≤n≤6×10^4,1≤t≤1.2×10^5).
The next t lines, each line contains two positive integers x,y(1≤x≤y≤(n+1)/2), denoting a given black position.

For each test case:
A single line contains a nonnegative integer, denoting the answer.