#include <bits/stdc++.h>
using namespace std;
// https://space.bilibili.com/672346917

#ifndef LOCAL
#define LOG(...) 42
#endif

#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long LL;
typedef pair <int, int> PII;

constexpr int inf = 0x3f3f3f3f;
constexpr double EPS = 1e-8;
const double PI = acos(-1);

int multi_cases = 1;

const int N = 2100;
PII a[N];

int do_init = 0;

int prime[300010];
bool st[300010];
int cnt = 0;

void init() {
    if (do_init) return;
    do_init = 1;
    st[1] = st[0] = 1;
    
    for (int i = 2; i <= 300000; i++) if (!st[i]) {
        prime[cnt++] = i;
        for (int j = i + i; j <= 300000; j += i) if (!st[j]) {
            st[j] = 1;
        }
    }
}

constexpr int M = 2100;
void A_SOUL_AvA () {
    int n, m;
    cin >> n >> m;

    init();

    for (int i = 0; i < n; i++) {
        cin >> a[i].fi >> a[i].se;
    }

    vector <array<int, 3>> e;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            e.pb({i, j, abs(a[i].fi - a[j].fi) + abs(a[i].se - a[j].se)});
        }
    }

    sort(all(e), [&](auto &u, auto &v) {
        return u[2] < v[2];
    });

    LL ans = 0;
    bitset <M> f[n];
    for (auto [i, j, d] : e) {
        if (!st[d]) {
            ans += (f[i] ^ f[j]).count();
        }
        f[i][j] = 1, f[j][i] = 1;
    }
    cout << ans << endl;
}

int main () {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int T = 1;
    for (multi_cases && cin >> T; T; T--) {
        A_SOUL_AvA ();
    }

    return 0;
}