#P10974. [2015杭电多校]Root

    ID: 10116 传统题 15000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-试除法分解质因数原根BSGS哈希表线性同余方程扩展欧几里得算法快速幂

[2015杭电多校]Root

Root

Problem Description

Given a number sum(1≤sum≤100000000)sum(1\leq sum \leq 100000000),we have mm queries which contains a pair (xi,yix_i,y_i) and would like to know the smallest nonnegative integer kik_{i} satisfying xiki=yi mod px_i^{k_{i}}=y_i\ mod\ p when the prime number p (sum mod p=0)p\ (sum\ mod\ p = 0)(ps:00=10^0=1)

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≤sum≤100000000,1≤m≤100000)sum,m(1\leq sum\leq 100000000,1\leq m\leq 100000) in the first line. The next mm lines will contains two intgeers xi,yi(0≤xi,yi≤1000000000)x_i,y_i(0\leq x_i,y_i\leq1000000000)

Output

For each test case,output "Case #XX:" and mm lines.(XX is the case number) Each line cotain a integer which is the smallest integer for (xi,yix_i,y_i) ,if we can't find such a integer just output "-1" without quote.

Sample Input

1
175 2
2 1
2 3

Sample Output

Case #1:
0
3

Hint

175 =52∗7175\ =5^2*7 20 mod 5 = 12^0\ mod\ 5\ =\ 1 23 mod 7 = 12^3\ mod\ 7\ =\ 1 So the answer to (2,1) is 0

Author

UESTC

Source

2015 Multi-University Training Contest 7