#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
struct ed{int x,y,d;}e[2000*2001/2+5];
int pr[N+5],p[N+5],cnt=0;
int x[2005],y[2005];
int d[2005];
int T,n,m,tot;
bitset<2005> gr[2005],le[2005];
int main(){
    // freopen("a.in","r",stdin);
    pr[1]=1;
    for (int i=2;i<=N;++i){
        if (!pr[i]) p[++cnt]=i;   
        for (int j=1;j<=cnt && 1ll*i*p[j]<=N;++j){
            pr[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }

    // for (int i=1;i<=20;++i) printf("%d",pr[i]);

    for (scanf("%d",&T);T;--T){
        scanf("%d%d",&n,&m);tot=0;
        for (int i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]),gr[i].reset(),le[i].reset();
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                if (j!=i)
                    gr[i].set(j);
        for (int i=1;i<=n;++i)
            for (int j=i+1;j<=n;++j)
                e[++tot]=(ed){i,j,abs(x[i]-x[j])+abs(y[i]-y[j])};
        sort(e+1,e+1+tot,[](ed a,ed b){return a.d<b.d;});


        // for (int i=1;i<=tot;++i) printf("%d %d  %d\n",e[i].x,e[i].y,e[i].d);



        int ans=0;
        for (int i=1,it1=1,it2=1;i<=tot;++i){
            while (it1<=tot && e[it1].d<e[i].d){
                le[e[it1].x].set(e[it1].y);
                le[e[it1].y].set(e[it1].x);
                ++it1;
            }
            while (it2<=tot && e[it2].d<=e[i].d){
                gr[e[it2].x].flip(e[it2].y);
                gr[e[it2].y].flip(e[it2].x);
                ++it2;
            }
            if (!pr[e[i].d]){
                bitset<2005> t=(le[e[i].x]&gr[e[i].y])|(gr[e[i].x]&le[e[i].y]);
                ans+=t.count();

                // printf("%d  %d    %d     ",e[i].x,e[i].y,e[i].d);
                // for (int j=1;j<=n;++j)
                //     putchar(t[j]+'0');
                // puts("");
                // printf("     ");

                // for (int j=1;j<=n;++j){
                //     int d1=abs(x[e[i].x]-x[j])+abs(y[e[i].x]-y[j]);
                //     int d2=abs(x[e[i].y]-x[j])+abs(y[e[i].y]-y[j]);
                //     if ((d1-e[i].d)*(d2-e[i].d)<0) putchar('1');
                //     else putchar('0');
                // }
                // puts("");

            }
        }

        // printf("%d\n",ans);

        for (int i=1,j=1;i<=tot;){
            int tmp=0;
            while (j<=tot && e[j].d==e[i].d){
                tmp+=d[e[j].x]+d[e[j].y];
                ++d[e[j].x],++d[e[j].y];
                ++j;
            }
            // printf("%d %d   %d    ",i,j,tmp);

            // int sum=0;
            // for (int k=1;k<=n;++k)
            //     sum+=d[k]*(d[k]-1)/2;
            // printf("%d\n",sum);

            if (!pr[e[i].d]) ans+=tmp;
            while (i<j){
                --d[e[i].x],--d[e[i].y];
                ++i;
            }
        }

        for (int i=1;i<=n;++i) le[i].reset();
        for (int i=1;i<=n;++i)
            for (int j=i+1;j<=n;++j)
                if (abs(x[i]-x[j])+abs(y[i]-y[j])==2)
                    le[i][j]=1;
        for (int i=1;i<=n;++i)
            for (int j=i+1;j<=n;++j)
                if (abs(x[i]-x[j])+abs(y[i]-y[j])==2){
                    ans-=(le[i]&le[j]).count()*2;
                }
        printf("%d\n",ans);


    }
    return 0;
}