A Task for a Sixth Grader

You need to find a value of x such that:

x^2 ≡ a (mod m)

Input

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

Output

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

Examples