#include<bits/stdc++.h>
#define endl '\n'
//#define int long long 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int N = 2e3+10;
const int M = 2e5 + 100;
const int mod = 1e9+7;
const int INF=1e9;
const double PI=acos(-1);
const double eps=1e-10;
struct node{
	int p1,p2,dis;
	
	bool operator <(const node &t)const{
		return dis<t.dis;
	}
	
	
}e[N*N];
int a[N],b[N];
bitset<N> f[N];	


//筛,M为1e5就保证了筛的范围 
int p[N*N];	
int num[N*N];
int idx=0;
void init(){
	memset(p,true,sizeof(p));
	p[1]=false;			//不是素数 
	for(int i=2;i<=N;i++){
		if(p[i])num[++idx]=i;
		for(int j=1;j<=idx&&i*num[j]<=N;j++){
			p[i*num[j]]=false;
			if(i%num[j]==0)break;
		}
	} 
}	 
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		f[i].reset();
	}
	
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	
	int cnt=0; 
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			e[++cnt].p1=i;
			e[cnt].p2=j;
			e[cnt].dis=abs(a[i]-a[j])+abs(b[i]-b[j]);
			
		}
	}
	
	sort(e+1,e+1+cnt);
	
	
	int ans=0;
	//枚举当前这条边作为中位数边 
	for(int i=1;i<=cnt;i++){
		int p1=e[i].p1;
		int p2=e[i].p2;
		int dis=e[i].dis;
		if(p[dis]){							//如果是素数 
			ans+=(f[p1]^f[p2]).count();		 
		}
		//f[i]表示的是i去到的点j中，满足dist(i,j)小于当前这条边的j有哪些,这里有排序的作用 
		//这个异或操作就保证了p1和p2有一个点到j的距离小于等于dis,一个大于等于dis，绝妙 
		f[p1][p2]=1;
		f[p2][p1]=1; 
	}
	cout<<ans<<endl;
	
} 

signed main() {
//	std::ios::sync_with_stdio(false);
//	std::cin.tie(0);
	int T=1;
	init();
	cin>>T;
	while(T--) {
		solve();
	}
}

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/