Numbers or Fireworks

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    const int MOD = 998244353;

    int tc;
    cin >> tc;
    while (tc--) {
        int n, k;
        cin >> n >> k;

        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dx = x[i] - x[j];
                int dy = y[i] - y[j];
                if (dx * dx + dy * dy == k) {
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        }

        vector<int> color(n, -1);
        for (int s = 0; s < n; s++) {
            if (color[s] != -1) continue;
            color[s] = 0;
            queue<int> q;
            q.push(s);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (int to : g[v]) {
                    if (color[to] == -1) {
                        color[to] = color[v] ^ 1;
                        q.push(to);
                    }
                }
            }
        }

        vector<int> part[2];
        for (int i = 0; i < n; i++) part[color[i]].push_back(i);
        if (part[0].size() > part[1].size()) swap(part[0], part[1]);

        vector<int>& A = part[0];
        vector<int>& B = part[1];
        int K = (int)A.size();

        vector<int> pos(n, -1);
        for (int i = 0; i < K; i++) pos[A[i]] = i;

        vector<int> bmask;
        for (int b : B) {
            int mask = 0;
            for (int v : g[b]) {
                if (pos[v] != -1) mask |= 1 << pos[v];
            }
            bmask.push_back(mask);
        }

        int maxState = 1 << K;
        vector<int> dp(maxState), zeta(maxState);

        ll ans = 0;
        int allA = (1 << K) - 1;

        for (int S = 0; S <= allA; S++) {
            int comp[16];
            int m = 0;
            for (int i = 0; i < K; i++) {
                if ((S >> i & 1) == 0) comp[i] = m++;
            }

            int sz = 1 << m;
            fill(dp.begin(), dp.begin() + sz, 0);
            dp[0] = 1;

            int notS = allA ^ S;

            for (int fullMask : bmask) {
                int c = __builtin_popcount((unsigned)(fullMask & S)) + 1;

                for (int mask = 0; mask < sz; mask++) zeta[mask] = dp[mask];

                int oldNeighbors = fullMask & notS;
                int neigh = 0;
                for (int i = 0; i < K; i++) {
                    if (oldNeighbors >> i & 1) neigh |= 1 << comp[i];
                }

                for (int bitId = 0; bitId < m; bitId++) {
                    if ((neigh >> bitId & 1) == 0) continue;
                    int bit = 1 << bitId;
                    for (int base = 0; base < sz; base += bit << 1) {
                        for (int off = 0; off < bit; off++) {
                            int& val = zeta[base + bit + off];
                            val += zeta[base + off];
                            if (val >= MOD) val -= MOD;
                        }
                    }
                }

                for (int mask = 0; mask < sz; mask++) {
                    dp[mask] = ((ll)dp[mask] * c + zeta[mask]) % MOD;
                }
            }

            for (int mask = 0; mask < sz; mask++) {
                ans += dp[mask];
                if (ans >= MOD) ans -= MOD;
            }
        }

        ans = (ans - 1 + MOD) % MOD;
        cout << ans << char(10);
    }
}