#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

constexpr int N = 2e5;
vector<int> primes;
vector<bool> isPrime(N + 1, true);
    
void solve() {
	int n, m;
	cin >> n >> m;
	vector<array<int, 2>> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i][0] >> a[i][1];
	}
	vector<array<int, 3>> g;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			g.push_back({abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]), i, j});
		}
	}
	sort(g.begin(), g.end());
	i64 ans = 0;
	vector<bitset<2000>> f(n);
	for (auto &[w, u, v] : g) {
		if (isPrime[w]) {
			ans += (f[u] ^ f[v]).count();
		}
		f[u][v] = 1, f[v][u] = 1;
	}
	cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        for (auto &p : primes) {
            if (i * p > N) {
                break;
            }
            isPrime[i * p] = false;
            if (i % p == 0) {
                break;
            }
        }
    } 
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}