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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX_PR = 5'000'000;
bitset<MAX_PR> isprime;
vi eratosthenesSieve(int lim) {
	isprime.set(); isprime[0] = isprime[1] = 0;
	for (int i = 4; i < lim; i += 2) isprime[i] = 0;
	for (int i = 3; i*i < lim; i += 2) if (isprime[i])
		for (int j = i*i; j < lim; j += i*2) isprime[j] = 0;
	vi pr;
	rep(i,2,lim) if (isprime[i]) pr.push_back(i);
	return pr;
}

int dist(pair<int, int> a, pair<int, int> b) {
	return abs(a.first - b.first) + abs(a.second - b.second);
}

ll countTri(int n, vector<pair<int, int>> p) {
	ll ans = 0;
	vector<bitset<2000>> adj(n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dist(p[i], p[j]) == 2) {
				adj[i][j] = 1;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (adj[i][j]) {
				ans += (adj[i] & adj[j]).count();
			}
		}
	}
	return ans/3;
}

ll countFull(int n, int m, vector<pair<int, int>> p) {
	ll ans = 0;
	vector<vector<pair<int, int>>> pps(2*m + 1);
	vector<bitset<2000>> lo(n), hi(n);
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			hi[i][j] = hi[j][i] = 1;
			int d = dist(p[i], p[j]);
			pps[d].emplace_back(i, j);
		}
	}

	vector<int> deg(n);
	for (int d = 1; d <= 2*m; d++) {
		for (auto [i, j]: pps[d]) {
			hi[i][j] = hi[j][i] = 0;
		}

		if (isprime[d]) {
			for (auto [i, j]: pps[d]) {
				deg[i]++; deg[j]++;
				ans += (lo[i] & hi[j]).count();
				ans += (lo[j] & hi[i]).count();
			}
			for (int i = 0; i < n; i++) {
				ans += 1LL*deg[i]*(deg[i]-1)/2;
				deg[i] = 0;
			}
		}

		for (auto [i, j]: pps[d]) {
			lo[i][j] = lo[j][i] = 0;
		}
	}
	
	return ans;
}

void solve() {
	int n, m; cin >> n >> m;
	vector<pair<int, int>> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i].first >> p[i].second;
	}

	ll ans = 0;
	ans -= countTri(n, p)*2;
	ans += countFull(n, m, p);

	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0); 
	eratosthenesSieve(200005);

	int t; cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}