#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define endl "\n"
#define PII pair<int,int>
const ll INF=0x3f3f3f3f;//3f3f3f3f;
const int mod=998244353;
const int N=4e6+5;
int pr[N],cnt;
bool st[N];
void init(){
	st[1]=1;
	for(int i=2;i<N;i++){
		if(!st[i]) pr[++cnt]=i;
		for(int j=1;pr[j]*i<N;j++){
			st[pr[j]*i]=1;
			if(i%pr[j]==0) break;
		}
	}
}
bitset<2005>p[2005];
struct Node{
	int v,a,b;
}e[N];
int x[2005],y[2005];
void solve(){
	int n,m; cin>>n>>m;
	for(int i=1;i<=n;i++) p[i].reset();
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	auto get=[&](int i,int j){
		return abs(x[i]-x[j])+abs(y[i]-y[j]);
	};
	int tot=0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++) e[++tot]={get(i,j),i,j};
	}
	sort(e+1,e+1+tot,[&](auto &t1,auto &t2){
		return t1.v<t2.v;
	});
	ll ans=0;
	for(int i=1;i<=tot;i++){
		auto &[v,a,b]=e[i];
		if(!st[v]) ans+=(p[a]^p[b]).count();
		p[a][b]=p[b][a]=1;
	} cout<<ans<<endl;
}
int main(){
	init();
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; cin>>T;
    while(T--) solve();
}