CF2178I.Numbers or Fireworks

Now that all the presents have been delivered, the North Pole is finally at peace — and it's time to celebrate with a spectacular New Year's fireworks show!

The North Pole is modeled as the Cartesian plane, with $n$ cities located at distinct lattice points. You are also given an integer $k$.

For a proper subset$^{\text{∗}}$ $T$ of the cities ($T$ may be empty), we define its explosiveness as follows:

1. A firework is launched from every city in $T$.
2. For each city $c$ not in $T$, let $f$ be the number of fireworks launched from cities that are exactly $\sqrt{k}$ Euclidean distance$^{\text{†}}$ away from $c$. Assign the number $(f+1)$ to this city $c$.
3. The explosiveness of $T$ is the product of all numbers assigned in Step 2.

Compute the sum of the explosiveness of $T$ over all $2^n-1$ proper subsets $T$ of the cities. Since the answer may be large, output it modulo $998\,244\,353$.

$^{\text{∗}}$A proper subset is any subset which is not equal to the whole set.

$^{\text{†}}$The Euclidean distance between two points $(x, y)$ and $(p, q)$ is defined as $\sqrt{(x - p)^2 + (y - q)^2}$.

所有礼物都已送达，北极终于恢复了宁静——现在是时候用一场盛大的新年烟花秀来庆祝了！

北极被建模为笛卡尔平面，其上有 $n$ 座城市，分别位于互不相同的格点上。同时给定一个整数 $k$。

对于城市集合的一个真子集$^{\text{∗}}$ $T$（$T$ 可以为空集），我们定义其爆炸力如下：

1. 从 $T$ 中的每一座城市发射一枚烟花；
2. 对于每一座不在 $T$ 中的城市 $c$，设 $f$ 表示所有与 $c$ 的欧几里得距离恰好为 $\sqrt{k}$ 的城市所发射的烟花总数（即：这些城市属于 $T$，且到 $c$ 的距离恰为 $\sqrt{k}$）。将数值 $(f+1)$ 分配给该城市 $c$；
3. $T$ 的爆炸力即为步骤 2 中分配给所有不在 $T$ 中的城市的数值之积。

请计算所有 $2^n-1$ 个城市的真子集 $T$ 的爆炸力之和。由于答案可能很大，请对 $998\,244\,353$ 取模后输出。

$^{\text{∗}}$ 真子集是指不等于全集的任意子集。

$^{\text{†}}$ 两点 $(x, y)$ 与 $(p, q)$ 之间的欧几里得距离定义为 $\sqrt{(x - p)^2 + (y - q)^2}$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2\le n\le 31$, $1\leq k \leq2\cdot 10^4$).

Then $n$ lines follow, the $i$-th line containing two integers $x_i$ and $y_i$ ($1\leq x_i, y_i\leq 100$) — the $x$ and $y$ coordinates of the $i$-th city, respectively. It is guaranteed that the coordinates of the cities are pairwise distinct.

It is guaranteed that the sum of $n^3$ over all test cases does not exceed $31^3$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2\le n\le 31$，$1\leq k \leq2\cdot 10^4$）。

接下来是 $n$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1\leq x_i, y_i\leq 100$），分别表示第 $i$ 个城市的 $x$ 坐标和 $y$ 坐标。保证所有城市的坐标两两不同。

保证所有测试用例的 $n^3$ 之和不超过 $31^3$。

For each test case, print a single integer — the sum, modulo $998\,244\,353$, of the explosiveness over all proper subsets $T$ of the cities.

对于每个测试用例，输出一个整数——即所有城市真子集 $T$ 的爆炸性之和对 $998\,244\,353$ 取模的结果。

In the first test case, below are the $2^3-1=7$ possible placements of fireworks. The numbers assigned to cities not in $T$ are circled.

The total explosiveness is $(1\cdot 1\cdot 1)+(1\cdot 2)+(2\cdot 1)+(2\cdot 2)+(3)+(2)+(2)=16$.

In the second test case, there are $2^2-1=3$ possible placements of fireworks. For every placement, since $(1,1)$ and $(100,100)$ have a Euclidean distance of $\sqrt{(100-1)^2+(100-1)^2}=\sqrt{19\,602}\neq\sqrt{20\,000}$, none of the cities will have fireworks that are exactly $\sqrt{k}$ away. Thus, the number $1$ is assigned to every city without fireworks. Therefore, the explosiveness is $1$ for every $T$, and the answer is $1+1+1=3$.

在第一个测试用例中，以下是 $2^3-1=7$ 种可能的烟花布置方案。未在集合 $T$ 中的城市所分配的数字被标为圆圈。

总爆炸力为 $(1\cdot 1\cdot 1)+(1\cdot 2)+(2\cdot 1)+(2\cdot 2)+(3)+(2)+(2)=16$。

在第二个测试用例中，共有 $2^2-1=3$ 种可能的烟花布置方案。对于每一种布置，由于 $(1,1)$ 与 $(100,100)$ 的欧几里得距离为 $\sqrt{(100-1)^2+(100-1)^2}=\sqrt{19\,602}\neq\sqrt{20\,000}$，因此没有任何城市会恰好位于距某处烟花 $\sqrt{k}$ 的位置。于是，每个未布置烟花的城市均被分配数字 $1$。因此，对每个 $T$，其爆炸力均为 $1$，最终答案为 $1+1+1=3$。