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
rainy jain :
20160525 04:44:08
Last edit: 20160627 10:10:38 

Pranjali Pratik:
20121116 06:44:43
@HWK : Can you take a look at solution 8062878? I can't place what the error may be. 

Ajey Golsangi:
20120707 17:10:34
The ans for (4,2) is 0 

praveen123:
20120615 18:46:48
If a function is not defined for some value , then how can you ask us to predict its value at that point.


HWK:
20110723 10:27:23
@blashyrkh: I don't believe that the mathworld definition is really better then the wiki one but I changed it as desired. Last edit: 20110722 07:30:17 

blashyrkh:
20110723 10:27:23
@HWK: Change it in a different way, please. Give a link to mathworld definition and remove a caution. Let the problem be more interesting. 

HWK:
20110723 10:27:23
Changed problem description. 

Michael T:
20110723 10:27:23
@HWK: It definitely does. Problem is en.wiki states: "let p be an odd prime number" in definition. So maybe you should have used mathworld instead. Where poddprime is only an "if". Last edit: 20110721 10:15:58 

HWK:
20110723 10:27:23
For the participants which understand German: http://de.wikipedia.org/wiki/LegendreSymbol


Hagen von Eitzen:
20110723 10:27:23
In the wikipedia article the problem links to, the Legendre symbol is *explicitly* not defined for p=2.

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