//time complexity O(N + K)

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <string.h>
#include <cmath>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <cstdlib>

#define X first
#define Y second

typedef long long ll;

using namespace std;

const int MAXN = 1000100;
bool waspl[MAXN + MAXN], wasmn[MAXN + MAXN];
int n, k;

int myabs(int x) {
    if (x < 0) x = -x;
    return x;
}

int cntpl(int sum) {
    return n - myabs(n + 1 - sum);
}

int cntmn(int dif) {
    return n - myabs(dif);
}

int sumodd[MAXN + MAXN], sumeven[MAXN + MAXN];



void solve() {
    memset(waspl, 0, sizeof(waspl) );
    memset(wasmn, 0, sizeof(wasmn) );

    memset(sumeven, 0, sizeof(sumeven) );
    memset(sumodd, 0, sizeof(sumodd) );

    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; i++) {
        int xx, yy;
        scanf("%d%d", &xx, &yy);
        waspl[xx + yy] = 1;
        wasmn[xx - yy + MAXN] = 1;
    }

    long long ans = 0;
    for (int i = 2; i <= n + n; i++) {
        if (waspl[i]) {
            ans += cntpl(i);
        }
    }

    for (int i = -n + 1; i <= n - 1; i++) {
        if (wasmn[i + MAXN]) {
            ans += cntmn(i);
        }
    }
    for (int i = 2; i <= n + n; i++) {
        if (i % 2 == 1) {
            sumodd[i] = sumodd[i - 2] + waspl[i];
        }
        else {
            sumeven[i] = sumeven[i - 2] + waspl[i];
        }
    }

    for (int i = -n + 1; i < n; i++) {
        if (!wasmn[i + MAXN] ) {
            continue;
        }

        int minpl = 2 + myabs(i), maxpl = n + n - myabs(i);

        if (minpl % 2 == 0) {
            ans -= sumeven[maxpl] - sumeven[minpl - 2];
        }
        else {
            ans -= sumodd[maxpl] - sumodd[minpl - 2];
        }
    }
    cout<<(ll)n*n - ans<<endl;
}

int main() {
    int test = 1;
    scanf("%d", &test);
    while (test--) {
        solve();
    }
    return 0;
}