Jacobi symbol

Consider a prime number p and an integer a !≡ 0 (mod p). Then a is called a quadratic residue mod p if there is an integer x such that x² ≡ a (mod p), and a quadratic non residue otherwise. Lagrange introduced the following notation, called the Legendre symbol, L (a,p):



For the calculation of these symbol there are the following rules, valid only for distinct odd prime numbers p, q and integers a, b not divisible by p:



The Jacobi symbol, J (a, n) ,is a generalization of the Legendre symbol ,L (a, p).It defines as :
1.  J (a, n) is only defined when n is an odd.
2.  J (0, n) = 0.
3.  If n is a prime number, J (a, n) = L(a, n).
4.  If n is not a prime number, J (a, n) = J (a, p1) *J (a, p2)…* J (a, pm), p1…pm is the prime factor of n.

Two integer a and n, 2 < a< =10⁶，2 < n < =10⁶，n is an odd number.

Output J (a,n)

3 5
3 9
3 13

-1
0
1

alpc41

2010 ACM-ICPC Multi-University Training Contest（15）——Host by NUDT