The number x is called a square root of a modulo n (root(a,n)) if x*x = a (mod n). Write the program to find the square root of number a by given modulo n.
Input
One number K in the first line is an amount of tests (K ≤ 100000). Each next line represents separate test, which contains integers a and n (1 ≤ a, n ≤ 32767, n is prime, a and n are relatively prime).
Output
For each input test the program must evaluate all possible values root(a,n)
in the range from 1 to n − 1 and output them in increasing order in one separate line using spaces. If there is no square root for current test, the program must print in separate line: ‘No root’.
Sample
input | output |
---|
5
4 17
3 7
2 7
14 31
10007 20011
| 2 15
No root
3 4
13 18
5382 14629
|
Problem Author: Michael Medvedev