Chef and Programming Contest by His Friend

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Fehc is Chef's best friend. They grew up with each other, and often help each other with competitive programming.
Chef is participating in a programming contest prepared by Fehc and finds the following problem in Fehc's problem set: given a string s[1..N], count the number of pairs of indices 1 ≤ i ≤ j ≤ N such that s[i..j] is palindrome and ji is even. The characters that may appear in s are 0, 1, 2, ..., 10^{9}.
Chef doesn't know the solution, but he knows Fehc's habits of creating test data. When preparing data for a string problem, Fehc always generates a string of N 0's, and replaces some of the 0's by other characters. Thus, Chef assumes that there are only K nonzero characters in s, and K is usually much smaller than N.
Given this useful information, can you help Chef solve this problem?
Input
 The first line of input contains one integer T denoting the number of test cases.
 For each test case, the first line contains two spaceseparated integers N and K.
 K lines follow; the ith of these lines contains two spaceseparated integers p_{i} and q_{i}, meaning that the ith nonzero character is s[p_{i}] = q_{i}.
Output
For each test case, output one integer denoting the answer to the problem.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^{9}
 0 ≤ K ≤ 10^{5}
 1 ≤ p_{1} < p_{2} < ... < p_{K} ≤ N
 1 ≤ q_{i} ≤ 10^{9}
Subtask #1 (9 points):
 N ≤ 1000
Subtask #2 (14 points):
 N ≤ 10^{5}
Subtask #3 (21 points):
 K ≤ 1000
Subtask #4 (56 points):
 original constraints
Example
Input: 3 7 2 5 1 6 1 7 3 2 1 4 2 6 1 10 0 Output: 9 12 30
Explanation
Example case 1: s={0,0,0,0,1,1,0}. The 9 pairs (i,j) are: (1,1), (2,2), ..., (7,7), (1,3) and (2,4).
Example case 2: s={0,1,0,2,0,1,0}.
Example case 3: s={0,0,0,0,0,0,0,0,0,0}.
Author:  r_64 
Editorial  https://discuss.codechef.com/problems/CHEFPCHF 
Tags  binarysearch, hashing, ltime52, medium, palindromes, r_64 
Date Added:  22092017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions