ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## 1132. Square Root

Time limit: 1.0 second
Memory limit: 64 MB
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

inputoutput
```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