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
rainy jain : 2016-05-25 04:44:08

Last edit: 2016-06-27 10:10:38
Pranjali Pratik: 2012-11-16 06:44:43

@HWK : Can you take a look at solution 8062878? I can't place what the error may be.

Ajey Golsangi: 2012-07-07 17:10:34

The ans for (4,2) is 0

praveen123: 2012-06-15 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.
For prime p = 2 ,,, even definitions on wikipedia do not give one answer ,
if a is divisible by 2 ,, then what should be answer ,,, it can be 0 and 1 as well. So please properly define your function .

HWK: 2011-07-23 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: 2011-07-22 07:30:17
blashyrkh: 2011-07-23 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: 2011-07-23 10:27:23

Changed problem description.

Michael T: 2011-07-23 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 p-odd-prime is only an "if".

Last edit: 2011-07-21 10:15:58
HWK: 2011-07-23 10:27:23

For the participants which understand German: http://de.wikipedia.org/wiki/Legendre-Symbol
Here you find a definition for L(a,2). But I thought that the majority don't understand German so I inserted the link to the English wikipedia page.
But anyway: In my problem I ask for the 'Legendre symbol' for p is prime but not p is odd. So also the answer for p=2 is expected.
Sorry for the trouble but I think it makes the problem slightly more interesting.

Hagen von Eitzen: 2011-07-23 10:27:23

In the wikipedia article the problem links to, the Legendre symbol is *explicitly* not defined for p=2.
Hence I don't see why there is so much discussion about "the even prime" here becasue any input case with p=2 would be illegal/the output undefined.


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