// Author:  HolyK
// Created: Sat Sep  3 16:14:19 2022
#include <bits/stdc++.h>

template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
using namespace std;
const int N = 2001, M = 2e5 + 1;

struct node {
  int x, y;
  
  void in() {
    cin >> x >> y;
  }
} a[N];
struct pr {
  int d, i, j;

  friend bool operator < (const pr &a, const pr &b) {
    return a.d < b.d;
  }
} z[N * N];
bitset<N> s[N], o, p;
bool v[M];

void solve() {
  int n, m; cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    a[i].in();
  }
  int tp = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
      int d = abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y);
      z[++tp] = {d, i, j};
    }
  }
  sort(z + 1, z + tp + 1);
  for(int i = 1; i <= n; i++) s[i].reset();
  o.reset();
  for(int i = 1; i <= n; i++) o.set(i);
  int ans = 0;
  for(int i = 1; i <= tp; i++) {
    if(v[z[i].d]) continue;
    s[z[i].i][z[i].j] = s[z[i].j][z[i].i] = 1;
    p = (~s[z[i].i]) & s[z[i].j];
    p[z[i].i] = p[z[i].j] = 0;
    ans += p.count();
    p = (~s[z[i].j]) & s[z[i].i];
    p[z[i].i] = p[z[i].j] = 0;
    ans += p.count();
  }
  cout << ans << '\n';
}

int main() {
  // freopen("t.in", "r", stdin);
  
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int t = 1;
  
  std::cin >> t;
  v[1] = 1;
  for(int i = 2; i < M; i++) {
    if(v[i]) continue;
    for(int j = 2 * i; j < M; j += i) v[j] = 1;
  }
  
  while (t--) {
    solve();
  }
  return 0;
}