Puppy and cats

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Tuzik is a very brave puppy. But there is still one thing he is afraid of  big black cats. He always tries to avoid them.
Tuzik's city can be represented as an N x N grid. Each cell of the city can either contain cats or not. Tuzik knows that K cells of the city are dumps. If a cell is a dump, then each diagonal that contains this cell is full of cats (all cells of this diagonal contain cats). Two cells with corresponding coordinates (i, j) and (x, y) are on one diagonal if either x + y equals i + j or x  y equals i  j.
You are given integers N and coordinates of K dumps. Please find the number of cells which are free of cats.
Input
The first line of the input contains an integer T, denoting the number of test cases. Each test case starts with a line containing spaceseparated integers N and K. Each of the following K lines contain two spaceseparated integers x_{i} and y_{i}  coordinates of each dump. All the dumps are pairwise different.
Output
For each test case, output a single line containing one integer  number of cells that are free of cats.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^{6}
 0 ≤ K ≤ 10^{5}
 1 ≤ x_{i}, y_{i} ≤ N
 Subtask #1 [22 points]: 1 ≤ N ≤ 500, 0 ≤ K ≤ 10^{4}
 Subtask #2 [24 points]: 1 ≤ N ≤ 1000, 0 ≤ K ≤ 10^{5}
 Subtask #3 [23 points]: 1 ≤ N ≤ 10^{6}, 0 ≤ K ≤ 1
 Subtask #4 [31 points]: no additional constraints
Example
Input: 1 3 2 1 2 3 2 Output: 5
Sample explanation
We have cells (2, 1) (2, 3) on the same diagonals with (1, 2) or (3, 2). Thus 4 cells are occupied by cats and 5 are free of cats.
Author:  pavel1996 
Tester:  zedthirtyeight 
Editorial  http://discuss.codechef.com/problems/PUPPYCT 
Tags  ltime26, pavel1996 
Date Added:  20072015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 