Given 2 integers a and p (1 ≤ a, p ≤ 1000000, p is prime) calculate the Legendre symbol (a/p).

Input

In the first line the number of test cases t < 100000. Then t lines with the 2 integers a and p.

Output

t lines with the Legendre symbol (a/p).

Example

Input:
4
2 7
5 7
14 7
3 2

Output:
1
-1
0
1