Root

Given a number sum(1≤sum≤100000000),we have m queries which contains a pair (xi,yi) and would like to know the smallest nonnegative integer kisatisfying xkii=yi mod p when the prime number p (sum mod p=0)(ps:00=1)

The first line contains a number T, indicating the number of test cases.

For each case, each case contains two integers sum,m(1≤sum≤100000000,1≤m≤100000) in the first line.

The next m lines will contains two intgeers xi,yi(0≤xi,yi≤1000000000)

For each test case,output "Case #X:" and m lines.(X is the case number)

Each line cotain a integer which is the smallest integer for (xi,yi) ,if we can't find such a integer just output "-1" without quote.

1
175 2
2 1
2 3

Case #1:
0
3

$175\ =5^2*7$  $2^0\ mod\ 5\ =\ 1$  $2^3\ mod\ 7\ =\ 1$  So the answer to (2,1) is 0

2015 Multi-University Training Contest 7