LEGRENDS - Legendre symbol

no tags 

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

hide comments
HWK: 2011-07-23 10:27:23

@setsquare: Interesting things in your solution but with a faster algorithm it could be almost 0.2 secs faster.


Added by:HWK
Date:2011-07-11
Time limit:3.049s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64