// Author : hejinming2012
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define dbg(x) cout << #x " = " << (x) << endl
#define quickio ios::sync_with_stdio(false);
#define quickin cin.tie(0);
#define quickout cout.tie(0);
#define maxn 2005
#define maxm 200005
using namespace std;
inline int read() {
    int now = 0, nev = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') nev = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { now = (now << 1) + (now << 3) + (c & 15); c = getchar(); }
    return now * nev;
}
void write(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
struct node {
    int u, v, w;
    bool operator < (const node &x) const {
        return w < x.w;
    }
};
int n, m, cnt, X[maxn];
int Y[maxn], prime[maxm];
bool is[maxm];
vector <node> vec;
bitset <maxn> Set[maxn];
int dis(int x, int y) {
    return abs(X[x] - X[y]) + abs(Y[x] - Y[y]);
}
signed main() {
    quickio
    quickin
    quickout
    n = 2e5, is[0] = is[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!is[i]) prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            is[i * prime[j]] = 1;
            if(i % prime[j] == 0) break ;
        }
    }
    int T = read();
    while(T--) {
        int n = read(), m = read();
        vec.clear();
        for(int i = 0; i < n; i++) {
            X[i] = read(), Y[i] = read();
            for(int j = 0; j < i; j++)
                vec.push_back((node) {j, i, dis(i, j)});
            Set[i].reset();
        }
        sort(vec.begin(), vec.end());
        int ans = 0;
        for(auto i : vec) {
            int u = i.u, v = i.v, w = i.w;
            if(!is[w]) ans += (Set[u] ^ Set[v]).count();
            Set[u][v] = Set[v][u] = 1;
        }
        write(ans), putchar(10);
    }
    return 0;
}