#include <bits/stdc++.h>

using i64 = long long;
constexpr int N = 2000, M = 2e5;

std::vector<int> pri;
std::vector<bool> vis;

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::pair<int, int>> a(n);
    for (auto &[x, y] : a) {
        std::cin >> x >> y;
        --x, --y;
    }

    std::vector<std::tuple<int, int, int>> edges;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int x = std::abs(a[i].first - a[j].first) + std::abs(a[i].second - a[j].second);
            edges.emplace_back(x, i, j);
        }
    }

    std::sort(edges.begin(), edges.end());
    std::vector<std::bitset<N>> adj(n);
    i64 ans = 0;
    for (auto [w, u, v] : edges) {
        if (!vis[w]) {
            ans += (adj[u] & ~adj[v]).count();
            ans += (~adj[u] & adj[v]).count();
        }
        adj[u].set(v);
        adj[v].set(u);
    }

    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    vis.resize(M + 1);
    for (int i = 2; i <= M; ++i) {
        if (!vis[i]) {
            pri.push_back(i);
        }
        for (auto p : pri) {
            if (i * p > M) {
                break;
            }
            vis[i * p] = true;
            if (i % p == 0) {
                break;
            }
        }
    }

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}