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
Noszály Csaba: 2011-07-23 10:27:23

i don't know that my solution fails only on p=2 or not, but i am curious what is the definition of (a/2), considering that
-1=1(mod 2).

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

@anubhav gupta: Rethink your calculation for the even prime. ;-)

Last edit: 2011-07-14 19:58:35
anubhav gupta: 2011-07-23 10:27:23

@HWK for even prime if have calculated the value but still wa

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

@anubhav gupta: Think of an even prime. ;-)

anubhav gupta: 2011-07-23 10:27:23

@HWK can u check soution id 5377398. its giving wa. can u tel me why??

shinoda: 2011-07-23 10:27:23

@HWK why i'm getting WA?? i've tested some test cases and is working fine... can you see my last submissions?

AC! ;)

Last edit: 2011-07-13 23:57:19
HWK: 2011-07-23 10:27:23

@Problem Solver: Thank you. :-)
Would you try to beat 0.12 secs? ;-)

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?


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