Div

x의 거듭제곱들로 이루어진 부호 있는 합이 x^0 + x^1 + ... + x^(m-1)로 나누어떨어지는 양의 정수 x의 개수를 세고, 무한히 많으면 -1을 출력한다.

어려움9정수론수학완전 탐색구현아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제1

문제

How many integers x > 0 exist such that c0xa0 + c1xa1 + . . . + cn−1xan−1 is divisible by x0 + x1 + . . . + xm−1?

입력

The first line contains a single integer t (1 ≤ t ≤ 105), denoting the number of test cases.

Each test case is described with two integers n and m (1 ≤ n ≤ 105; 1 ≤ m ≤ 109), followed by n lines containing a pair of integers ci and ai each (|ci| = 1; 0 ≤ ai ≤ 109).

The sum of n over all test cases does not exceed 105.

출력

For each test case, display the required number, or −1 if it is infinite.