Gospodin Malnar 制作了一张披萨，上面有 $n$ 个辣椒，第 $i$ 个辣椒的坐标为 $(x_i, y_i)$。我们可以将披萨想象成从点 $(0, 0)$ 到点 $(m, m)$ 的正方形。现在他想和他的朋友 Ivan 分享这张披萨。

Gospodin Malnar 将沿着一条特定的直线切割披萨。此外，如果一条直线可以写成 $y = ax + b$ 的形式，其中 $a$ 和 $b$ 均为整数，则称该直线为“整系数直线”。为了公平地与 Ivan 分享披萨，需要选择一条整系数直线，使得直线两侧的辣椒数量相等，且直线不能经过任何一个辣椒。

为了帮助他们，请输出满足条件的直线数量，如果存在无穷多条，则输出 $-1$。

输入格式

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^6$)，$n$ 为偶数，($1 \le m \le 10^5$)。接下来的 $n$ 行包含辣椒的坐标 $x_i$ 和 $y_i$ ($0 \le x_i, y_i < m$)。

所有测试用例的 $n$ 之和不超过 $10^6$，所有测试用例的 $m$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出满足条件的直线数量，如果存在无穷多条，则输出 $-1$。

样例

输入 1

1
2 2
0 1
1 0

输出 1

-1

输入 2

1
6 6
2 0
2 1
0 3
4 3
1 4
3 5

输出 2

4

输入 3

1
6 10
0 0
5 0
5 0
4 9
9 9
9 9

输出 3

36