#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int T;
	cin >> T;
	for(int t =0; t < T; t++) {
		int N,K;
		cin >> N >> K;
		vector<int> P(K),Q(K);
		for(int i =0; i < K; i++) {
			cin >> P[i] >> Q[i];
			P[i]--;
		}
		if(K == 0) {
			if(N%2) cout << 1LL*(N/2+1)*(N/2+1) << "\n";
			else cout << 1LL*(N/2)*(N/2+1) << "\n";
			continue;
		}
		vector<int> D(K-1);
		for(int i =0; i < K-1; i++) D[i] =P[i+1]-P[i];
		cat mod =1000000009, p =999983;
		vector<cat> Hq(K+1,0), Hd(K,0), Hqi(K+1,0), Hdi(K,0), pp(K+1,1);
		for(int i =0; i < K; i++) Hq[i+1] =(p*Hq[i]+Q[i]+1)%mod;
		for(int i =0; i < K-1; i++) Hd[i+1] =(p*Hd[i]+D[i])%mod;
		for(int i =K-1; i >= 0; i--) Hqi[i] =(p*Hqi[i+1]+Q[i]+1)%mod;
		for(int i =K-2; i >= 0; i--) Hdi[i] =(p*Hdi[i+1]+D[i])%mod;
		for(int i =1; i <= K; i++) pp[i] =(pp[i-1]*p)%mod;
		
		cat ans =0;
		vector<cat> L0;
		for(int i =0; i < K; i++) L0.push_back(P[i]-((i == 0)?0:(P[i-1]+1)));
		L0.push_back(N-1-P[K-1]);
		ALL_THE(L0,it) {
			if((*it)%2) ans +=(*it/2+1)*(*it/2+1);
			else ans +=(*it/2)*(*it/2+1);
		}

		for(int i =0; i < K; i++) {
			// centered at P[i]
			int a =0, b =min(i+1,K-i);
			while(b-a > 1) {
				int c =(a+b)/2;
				cat hq =Hq[i+c+1]-Hq[i-c]*pp[2*c+1], hqi =Hqi[i-c]-Hqi[i+c+1]*pp[2*c+1];
				cat hd =Hd[i+c]-Hd[i-c]*pp[2*c], hdi =Hdi[i-c]-Hdi[i+c]*pp[2*c];
				if((hq-hqi)%mod == 0 && (hd-hdi)%mod == 0) a =c;
				else b =c;
			}
			int l =P[i]+1, r =N-P[i];
			if(i-b >= 0) l =min(l,P[i]-P[i-b]);
			if(i+b < K) r =min(r,P[i+b]-P[i]);
			ans +=min(l,r);
		}

		for(int i =0; i < K-1; i++) if(D[i]%2 == 0 && Q[i] == Q[i+1]) {
			// centered between P[i] and P[i+1]
			int mid =(P[i]+P[i+1])/2;
			int a =0, b =min(i+1,K-1-i);
			while(b-a > 1) {
				int c =(a+b)/2;
				cat hq =Hq[i+c+2]-Hq[i-c]*pp[2*c+2], hqi =Hqi[i-c]-Hqi[i+c+2]*pp[2*c+2];
				cat hd =Hd[i+c+1]-Hd[i-c]*pp[2*c+1], hdi =Hdi[i-c]-Hdi[i+c+1]*pp[2*c+1];
				if((hq-hqi)%mod == 0 && (hd-hdi)%mod == 0) a =c;
				else b =c;
			}
			int l =mid+1, r =N-mid;
			if(i-b >= 0) l =min(l,mid-P[i-b]);
			if(i+1+b < K) r =min(r,P[i+1+b]-mid);
			ans +=min(l,r)-(mid-P[i]);
		}

		cout << ans << "\n";
	}
	return 0;}

// look at my code
// my code is amazing