有一支由 $n$ 名士兵组成的队伍被派往 Byteland 的某个地方。目前，第 $i$ 名士兵位于位置 $(x_i, y_i)$。士兵们即将出发，但目标位置尚不明确。

假设目标位置为 $(x_e, y_e)$。已知对于所有士兵，$(x_e, y_e)$ 均为范围 $[0, m]$ 内的非负整数。此外，对于第 $i$ 名士兵，他唯一知道的信息是 $(|x_i - x_e| + |y_i - y_e|) \pmod{k_i} = t_i$。

为了找到正确的目标位置，这些士兵正在利用他们目前掌握的信息进行分析。请编写一个程序，计算出可能的目标位置数量。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10, 1 \le m \le 10^9$)，分别表示士兵的数量和 $x_e, y_e$ 的上限。

接下来的 $n$ 行，每行包含四个整数 $x_i, y_i, k_i$ 和 $t_i$ ($0 \le x_i, y_i \le m, 2 \le k_i \le 5, 0 \le t_i < k_i$)，表示第 $i$ 名士兵掌握的信息。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示可能的目标位置数量。

样例

样例输入 1

2
2 5
1 2 4 2
3 1 2 1
2 5
1 2 4 2
1 2 4 3

样例输出 1

10
0