The '''[https://en.wikipedia.org/wiki/Jacobi_symbol Jacobi symbol]''' is a multiplicative function that generalizes the Legendre symbol. Specifically, the Jacobi symbol (a | n) equals the product of the Legendre symbols (a | p_i)^(k_i), where n = p_1^(k_1)*p_2^(k_2)*...*p_i^(k_i) and the Legendre symbol (a | p) denotes the value of  a ^ ((p-1)/2) (mod p)
* (a | p) ≡ &nbsp;  1  &nbsp; &nbsp; if a is a square (mod p)
* (a | p) ≡        -1  &nbsp; &nbsp; if a is not a square (mod p)
* (a | p) ≡ &nbsp;  0  &nbsp; &nbsp; if a ≡ 0 

If n is prime, then the Jacobi symbol (a | n) equals the Legendre symbol (a | n).

;Task:
Calculate the Jacobi symbol (a | n).

;Reference:
* [https://en.wikipedia.org/wiki/Jacobi_symbol Wikipedia article on Jacobi symbol].

