Migrated from Lutece 1188 Log

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given a number $sum(1\leq sum \leq 100000000)$,we have $m$ queries which contains a pair ($x_i,y_i$) and would like to know the smallest nonnegative integer $k_{i}$ satisfying $x_i^{k_{i}}=y_i\ mod\ p$ when the prime number $p\ (sum\ mod\ p = 0)$

Input

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

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

The next $m$ lines will contains two intgeers $x_i,y_i(0\leq x_i,y_i\leq1000000000)$

Output

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 ($x_i,y_i$) ,if we can't find such a integer just output "-1" without quote.

Samples

1
175 2
2 1
2 3

Case #1:
0
3

Note

$175\ =5^2*7$

$2^0\ mod\ 5\ =\ 1$

$2^3\ mod\ 7\ =\ 1$

So the answer to (2,1) is 0

Resources

Prepare for 2015 MU2015 Multi-University Training