시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 45 | 10 | 7 | 21.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.
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 2