#include <bits/stdc++.h>
using namespace std;
static constexpr int maxn = 2000 + 5;
static constexpr int maxc = 200000 + 5;

bool notprime[maxc];

bitset<maxn> pre[maxn], suf[maxn];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    notprime[0] = notprime[1] = true;
    for (int i = 2; i < maxc; ++i) {
        if (notprime[i]) continue;
        for (int j = i + i; j < maxc; j += i)
            notprime[j] = true;
    }
    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        vector<pair<int, int>> a(n);
        for (auto &[x, y] : a) cin >> x >> y;

        vector<tuple<int, int, int>> v;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int d = abs(a[i].first - a[j].first) + abs(a[i].second - a[j].second);
                v.emplace_back(d, i, j);
            }
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            pre[i].reset();
            for (int j = 0; j < n; ++j)
                if (i != j) suf[i][j] = true;
        }
        sort(v.begin(), v.end());
        for (auto [d, i, j] : v) {
            if (not notprime[d]) {
                ans += (pre[i] & suf[j]).count();
                ans += (pre[j] & suf[i]).count();
            }
            pre[i][j] = true;
            pre[j][i] = true;
            suf[i][j] = false;
            suf[j][i] = false;
        }
        cout << ans << '\n';
    }
    return 0;
}