Destroy the cube

Problem Description

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 $x$th row and the $y$th 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\leq x,y\leq n$, which shows it is quite symmetry. Also because of this, only the colors of the positions $(x,y)$ which satisfies $x\leq y\leq\lfloor\frac{n+1}{2}\rfloor$ 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.

Input

The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases. For each test case: The first line contains two positive integers $n,t(1\leq n\leq6\times10^4,1\leq t\leq1.2\times10^5)$. The next $t$ lines, each line contains two positive integers $x,y(1\leq x\leq y\leq\lfloor\frac{n+1}{2}\rfloor)$, denoting a given black position.

Output

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

Sample Input

2

3 1

2 2

5 2

2 3

3 3

Sample Output

20

76

Source

2017 Multi-University Training Contest - Team 7

https://acm.hdu.edu.cn/showproblem.php?pid=6123