#include<bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
#define inf 0x3f3f3f3f
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define mod (int)1e9+7
#define NO puts("NO")
#define YES puts("YES")
#define No puts("No")
#define Yes puts("Yes")
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=2010,M=N*N;
int n,m;
int a[N],b[N];
bitset<N>bset[N];//表示当前枚举了哪些边
struct P{
    int a,b,w;
    bool operator<(const P&x)const{
        return w<x.w;
    }
}p[M];
int prim[M],tot;
bool vis[M];
void prime(int M){
    vis[1]=1;//注意把1判定为非质数
    for(int i=2;i<=M;i++){
        if(!vis[i]) prim[tot++]=i;
        for(int j=0;prim[j]<=M/i;j++){
            vis[i*prim[j]]=1;
            if(i%prim[j]==0) break;
        }
    }
}
int get(int i,int j){
    return abs(a[i]-a[j])+abs(b[i]-b[j]);
}
inline void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++) bset[i].reset();
    for(int i=0;i<n;i++) cin>>a[i]>>b[i];
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            p[cnt++]={i,j,get(i,j)};
        }
    }
    sort(p,p+cnt);
    int ans=0;
    for(int i=0;i<cnt;i++){
        int a=p[i].a,b=p[i].b,w=p[i].w;
        if(!vis[w]) ans+=(bset[a]^bset[b]).count();
        bset[a][b]=bset[b][a]=1;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    mp.reserve(1024);
//    mp.max_load_factor(0.25);
    prime(M);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}