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
Problem Solver: 2011-07-23 10:27:23

Nice problem, didn't know this symbol :)

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

@Alex Anderson: To allow solutions in languages like Python etc.
@Paulo Roberto Santos de Sousa: Go for 0.12 secs. ;-)

Alex Anderson: 2011-07-23 10:27:23

Why is the time limit so high?

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