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
Mitch Schwartz: 2022-07-28 06:26:51

@Francky: It's great to see you here too. Email sent!

Francky: 2022-07-27 19:04:15

@Mitch, could you email me ? Happy to see you again here ;-)

Mitch Schwartz: 2022-07-22 13:32:38

In my view there is very little cause for confusion here. The usual definition for Legendre symbol (not the one using Euler's criterion, but the one that lists 3 cases) can be applied to p = 2 without any ambiguity or difficulty, provided you know what a quadratic residue is. If you happen to have some familiarity with the territory (quadratic reciprocity, Jacobi symbol), then you may get a good sense of why p = 2 is typically excluded from the definition, but for a programming exercise it seems good to encourage solvers to think about this case rather than, say, applying a formula blindly. Incidentally, the Kronecker symbol (a/n) uses a different definition for n = 2.

Last edit: 2022-07-22 21:03:44
vas14: 2022-07-22 03:54:57

Not sure why the author thinks including cases for p = 2 is "interesting." It takes more time to google the appropriate definition of quadratic residue for p = 2 than to actually solve this problem. To save people time, the answer to this problem for p = 2 will be 0 for even values of a and 1 otherwise.

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.


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