有多少个整数 $x > 0$ 满足 $c_0x^{a_0} + c_1x^{a_1} + \dots + c_{n-1}x^{a_{n-1}}$ 能被 $x^0 + x^1 + \dots + x^{m-1}$ 整除？

输入格式

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

每个测试用例包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^5$; $1 \le m \le 10^9$)，随后有 $n$ 行，每行包含一对整数 $c_i$ 和 $a_i$ ($|c_i| = 1$; $0 \le a_i \le 10^9$)。

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

输出格式

对于每个测试用例，输出满足条件的整数个数，如果个数无限，则输出 $-1$。

样例

输入 1

3
5 2
1 0
1 0
1 0
1 0
1 0
5 3
-1 2
-1 1
-1 0
1 1
-1 1
12 3
-1 0
-1 7
1 8
1 8
-1 4
-1 6
1 8
1 2
1 5
1 2
-1 9
1 5

输出 1

1
-1
2

说明

在第一个测试用例中，$x = 4$ 是唯一的解。

在第二个测试用例中，对于任意 $x > 0$，商均为 $-1$。

在第三个测试用例中，解为 $x = 2$ 和 $x = 9$。