#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "queue"
#include "vector"
#include "queue"
#include "stack"
#include "ctime"
#include "set"
#include "map"
#include "bitset"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 2e3 + 10;
const int P = 998244353;
int n , m , k;

vector<int> vx , vy;
int X[MAXN] , Y[MAXN] , dis[MAXN][MAXN];

int np[100006] , pri[100006] , en;
void sieve() {
	np[1] = 1;
	rep( i , 2 , 100006 ) {
		if( !np[i] ) pri[++ en] = i;
		for( int j = 1 ; j <= en && i * pri[j] < 100006 ; ++ j ) {
			np[i * pri[j]] = 1;
			if( i % pri[j] == 0 ) break;
		}
	}
}

int gx( int x ) {
	return lower_bound( all( vx ) , x ) - vx.begin() + 1;
}
int gy( int y ) {
	return lower_bound( all( vy ) , y ) - vy.begin() + 1;
}

int S[MAXN][MAXN];

int calc( int x1 , int y1 , int x2 , int y2 ) {
	int X = gx( x2 + 1 ) - 1 , Y = gy( y2 + 1 ) - 1 , x = gx( x1 ) - 1 , y = gy( y1 ) - 1;
	return S[X][Y] - S[X][y] - S[x][Y] + S[x][y];
}

int cn[100006] , tx[MAXN] , ty[MAXN];
map<pii,int> M;

void solve() {
	cin >> n >> m;
	vx.clear() , vy.clear();
	rep( i , 1 , n ) {
		int x , y;
		scanf("%d%d",&x,&y);
		tx[i] = x , ty[i] = y;
//		M[mp( x , y )] ++;
		X[i] = x - y , Y[i] = x + y;
		vx.pb( X[i] ) , vy.pb( Y[i] );
	}
	rep( i , 1 , n ) rep( j , 1 , n ) dis[i][j] = max( abs( X[i] - X[j] ) , abs( Y[i] - Y[j] ) );
	sort( all( vx ) ) , vx.erase( unique( all( vx ) ) , vx.end() );
	sort( all( vy ) ) , vy.erase( unique( all( vy ) ) , vy.end() );
	rep( i , 1 , n ) X[i] = lower_bound( all( vx ) , X[i] ) - vx.begin() + 1;
	rep( i , 1 , n ) Y[i] = lower_bound( all( vy ) , Y[i] ) - vy.begin() + 1;
	rep( i , 1 , n ) S[X[i]][Y[i]] ++;
	rep( i , 1 , vx.size() + 1 ) rep( j , 1 , vy.size() + 1 ) 
		S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
	int res = 0;
	rep( i , 1 , n ) rep( j , i + 1 , n ) if( !np[dis[i][j]] ) {
		int xi = vx[X[i] - 1] , yi = vy[Y[i] - 1] , xj = vx[X[j] - 1] , yj = vy[Y[j] - 1];
		int d = dis[i][j];
		res += calc( xi - d , yi - d , xi + d , yi + d ) + calc( xj - d , yj - d , xj + d , yj + d );
		if( abs( xi - xj ) > abs( yi - yj ) ) {
			if( xi > xj ) swap( xi , xj ) , swap( yi , yj );
			res -= 2 * calc( xi , max( yi - d , yj - d ) , xj , min( yi + d , yj + d ) );
		} else {
			if( yi > yj ) swap( xi , xj ) , swap( yi , yj );
			res -= 2 * calc( max( xi - d , xj - d ) , yi , min( xi + d , xj + d ) , yj );
		}
	}
	rep( i , 1 , n ) {
		int re = 0;
		rep( j , 1 , n ) if( !np[dis[i][j]] ) {
			re += cn[dis[i][j]] , ++ cn[dis[i][j]];
		}
		rep( j , 1 , n ) if( !np[dis[i][j]] ) {
			-- cn[dis[i][j]];
		}
		res -= re;
	}
	rep( i , 1 , vx.size() + 1 ) rep( j , 1 , vy.size() + 1 ) S[i][j] = 0;
//	rep( i , 1 , n ) rep( j , 1 , n ) if( i != j && !np[dis[i][j]] && tx[i] == tx[j] && ( ty[i] - ty[j] ) % 2 == 0 ) {
//		int Y = ( ty[i] + ty[j] ) / 2 , l = ( ty[i] - ty[j] ) / 2;
//		if( M.count( mp( tx[i] - l , Y ) ) ) res += 4;
//		if( M.count( mp( tx[i] + l , Y ) ) ) res += 4;
//	}
//	rep( i , 1 , n ) rep( j , 1 , n ) if( i != j && !np[dis[i][j]] && ty[i] == ty[j] && ( tx[i] - tx[j] ) % 2 == 0 ) {
//		int X = ( tx[i] + tx[j] ) / 2 , l = ( tx[i] - tx[j] ) / 2;
//		if( M.count( mp( X , ty[i] - l ) ) ) res += 4;
//		if( M.count( mp( X , ty[i] + l ) ) ) res += 4;
//	}
	cout << res << endl;
}

signed main() {
	sieve();
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}