Div

$x > 0$인 정수 $x$ 중에서 $c_0 x^{a_0} + c_1 x^{a_1} + \\cdots + c_{n-1} x^{a_{n-1}}$이 $1 + x + \\cdots + 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$를 넘지 않는다.

각 테스트 케이스마다 조건을 만족하는 정수 $x > 0$의 개수를 출력한다. 개수가 무한하면 $-1$을 출력한다.