Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

LEGENDRE - 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<100. 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

Added by:HWK
Date:2011-07-11
Time limit:8.909s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: SCM qobi

hide comments
2014-06-30 21:17:56 challenger
Thanks. I'd suggest removing some parts of your code without thinking whether it will work or not. You'll be surprised how many characters can you cut. ;-)
2014-06-30 16:53:01 Dominique VAILLANT
@challenger: 71 with Ruby, very impressive! I had almost no hope to shorten my actual (Ruby) code. Thanks!
2011-07-21 14:00:11 HWK
Changed problem description for clarification.

Edit: Changed again due to a remark at main SPOJ.

Last edit: 2011-07-22 07:32:29
2011-07-14 08:06:14 HWK
@hallvabo: Yes, but in few as builtin.
I guess your Bash solution is hard to beat even for Nabb.
2011-07-13 23:03:55 Hallvard Norheim Bø
@HWK: it exists in other languages too ;)
2011-07-13 21:48:55 HWK
@hallvabo: Seems it was too easy. Try to solve http://www.spoj.pl/problems/LEGRENDS/ . My Python solution requires 6.91 secs. ;-)

Last edit: 2011-07-13 21:50:53
2011-07-13 21:22:47 HWK
@hallvabo: Great!
My best Python solution requires 102 bytes. First I thought to ban the Python function you used. I already regret that I didn't it. :-)
So it will be difficult for Perl. Hi, Jander. I need 91 Perl bytes. ;-)

Last edit: 2011-07-13 21:35:52
2011-07-13 21:13:54 Hallvard Norheim Bø
Ok, that was logical. Actually it helped me save two bytes :)
2011-07-13 20:56:07 HWK
That is the interesting part. p has to be prime not an odd prime. But for 2 Euler's formula doesn't work. Do you understand German? Then look here: http://de.wikipedia.org/wiki/Legendre-Symbol

Last edit: 2011-07-13 20:56:31
2011-07-13 20:24:33 Hallvard Norheim Bø
What should the result be when p=2? According to the definitions I have seen, p must be an odd prime.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.