A Task for a Sixth Grader#4319
Sign in

A Task for a Sixth Grader

4 seconds
256 megabytes
Very hard

You need to find a value of such that:

x^2 \equiv a \pmod{m}

Input

The first line of the input contains the integer (1 \le k \le 50), which represents the number of test cases. Each of the following lines describes a test case with two integers: and (0 \le a \le 10^9, 1 \le m \le 10^9).

Output

For each test case, output the integer if it exists, or print IMPOSSIBLE if no such can be found.

Examples

Example 1

Loading
Loading