给定一个 $M \times M$ 的棋盘，上面有 $N$ 个点。你需要计算有多少种选择 3 个点的方法，使得这 3 个点两两之间的距离构成的集合中，中位数是一个质数。

$(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $T(1 \le T \le 10)$。 接下来是各测试用例的描述。 每个测试用例的第一行包含两个整数 $N, M$。 接下来的 $N$ 行，每行包含两个整数 $x_i, y_i$。 保证不存在 $i, j(i \neq j)$ 满足 $x_i = x_j$ 且 $y_i = y_j$。 $1 \le N \le 2000, 1 \le M \le 10^5, 1 \le x_i, y_i \le M$。

输出格式

对于每个测试用例，输出一个整数，即问题的答案。

样例

输入 1

2
3 3
1 1
2 2
3 3
3 3
1 1
2 1
3 2

输出 1

1
1