LEGRENDS  Legendre symbol
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:
20110723 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


HWK:
20110723 10:27:23
@anubhav gupta: Rethink your calculation for the even prime. ;) Last edit: 20110714 19:58:35 

anubhav gupta:
20110723 10:27:23
@HWK for even prime if have calculated the value but still wa 

HWK:
20110723 10:27:23
@anubhav gupta: Think of an even prime. ;) 

anubhav gupta:
20110723 10:27:23
@HWK can u check soution id 5377398. its giving wa. can u tel me why?? 

shinoda:
20110723 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?


HWK:
20110723 10:27:23
@Problem Solver: Thank you. :)


Problem Solver:
20110723 10:27:23
Nice problem, didn't know this symbol :) 

HWK:
20110723 10:27:23
@Alex Anderson: To allow solutions in languages like Python etc.


Alex Anderson:
20110723 10:27:23
Why is the time limit so high? 
Added by:  HWK 
Date:  20110711 
Time limit:  3.049s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 