#include <bits/stdc++.h>
#define N 2005
using i64 = long long;
using namespace std;

int n, m, x[N], y[N];
int dis(int a, int b)
{
    return abs(x[a] - x[b]) + abs(y[b] - y[a]);
}
struct node
{
    int x, y, len;
    bool operator<(const node &tmp) const
    {
        return len < tmp.len;
    }
} num[N * N];
int pri[200005], vis[200005], tot;
bitset<2005> s[N];
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i], s[i].reset();
    int cnt = 0;
    i64 ans = 0;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            num[++cnt] = {i, j, dis(i, j)};
    sort(num + 1, num + cnt + 1);
    for (int i = 1; i <= cnt; i++)
    {
        auto [u, v, w] = num[i];
        if (!vis[w])
            ans += (s[u] ^ s[v]).count();
        s[u][v] = s[v][u] = 1;
    }
    cout << ans << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 2; i <= 2e5; i++)
    {
        if (!vis[i])
            pri[++tot] = i;
        for (int j = 1; j <= tot && pri[j] * i <= 2e5; j++)
        {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}