B. 整除（div）

求有多少个正整数 $x$ 满足

$c_0x^{a_0}+c_1x^{a_1}+\cdots+c_{n-1}x^{a_{n-1}}$

能被

$x^0+x^1+\cdots+x^{m-1}$

整除，其中 $c$ 和 $a$ 是两个给定的序列。

输入格式

第一行一个整数 $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

子任务

• Subtask 1（10 points）： $t,n,m\le 10$。
• Subtask 2（30 points）： $t\le 10$，$n,m\le 1000$。
• Subtask 3（60 points）： 无额外限制。