시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB4510721.212%

문제

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.

예제 입력 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