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