#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200100;
vector<int>is_prime(N);
int solve(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>v(n);
    for( int i=0;i<n;i++){
        cin>>v[i].first>>v[i].second;
    }
    vector<array<int,3>>vv;
    for( int i=0;i<n;i++){
        for( int j=i+1;j<n;j++){
            vv.push_back({abs(v[i].first-v[j].first)+abs(v[i].second-v[j].second),i,j});
        }
    }
    sort(vv.begin(),vv.end());
    vector<bitset<2000>>W(2000),B(2000);
    //W[i][j]表示从i到j的线段没有被访问过
    //B[i][j]表示从i到j的线段有被访问过
    for( int i=0;i<2000;i++){
        W[i].set();
    }   
    int ans=0; 
    for( int i=0;i<vv.size();i++){
        int x=vv[i][1],y=vv[i][2];
        if(!is_prime[vv[i][0]]) {
            ans+=(W[x]&B[y]).count()+(W[y]&B[x]).count();
        }
        W[x][y]=0;W[y][x]=0;
        B[x][y]=1;B[y][x]=1;
    }
    return ans;


    
}
int main(){
    is_prime[1]=1;
    for( int i=2;i<N;i++){
        if(is_prime[i]==0){
            for( int j=i+i;j<N;j+=i){
                is_prime[j]=1;
            }
        }
    }
    int t;
    cin>>t;
    while(t--){
        cout<<solve()<<"\n";
    }

    system("pause");
}