18745번 - Div 다국어

문제

How many integers x > 0 exist such that c₀x^a₀ + c₁x^a₁ + . . . + c_n−1x^a_n−1 is divisible by x⁰ + x¹ + . . . + x^m−1?

입력

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

Each test case is described with two integers n and m (1 ≤ n ≤ 10⁵; 1 ≤ m ≤ 10⁹), followed by n lines containing a pair of integers c_i and a_i each (|c_i| = 1; 0 ≤ a_i ≤ 10⁹).

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

출력

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

제한

힌트