#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a) ; i < (b); i++)
#define _for(i, a, b) for(int i = (a) ; i <= (b); i++)
using namespace std;

typedef long long ll;
const int M = 1e5 + 10;
const int N = 2e3 + 10;
bool vis[M];
vector<int> p;
bitset<N> g[N];
int x[N], y[N], n, m;

struct Edge
{
	int u, v, w;
	bool operator < (const Edge& rhs) const
	{
		return w < rhs.w;
	}
};
vector<Edge> e;

void init()
{
	vis[0] = vis[1] = 1;
	_for(i, 2, 1e5)
	{
		if(!vis[i]) p.push_back(i);
		for(int x: p)
		{
			if(i * x > 1e5) break;
			vis[i * x] = 1;
			if(i % x == 0) break;
		}
	}
}
 
int main()
{
	init();

	int T; scanf("%d", &T);
	while(T--)
	{
		e.clear();
		scanf("%d%d", &n, &m);
		_for(i, 1, n) scanf("%d%d", &x[i], &y[i]), g[i].reset();

		_for(i, 1, n)
			_for(j, i + 1, n)
				e.push_back({i, j, abs(x[i] - x[j]) + abs(y[i] - y[j])});
		sort(e.begin(), e.end());

		ll ans = 0;
		for(auto [u, v, w] : e)
		{
			if(!vis[w]) ans += (g[u] ^ g[v]).count();
			g[u][v] = g[v][u] = 1;
		}
		printf("%lld\n", ans);
	}
 
	return 0;
}