MMFMOB - Möbius function


In number theory and combinatorics Möbius function μ(n) for integer n > 0 is defined as follows:

μ(1) = 1
μ(n) = (-1)k if n is the product of k (k > 0) distinct primes
μ(n) = 0 otherwise.

Given integer n > 0 compute μ(n).

Note: 11/06/2018 added new test case.

Input

Each line of input contains one random integer number 1 ≤ n ≤ 108 (100 000 000). Input terminates with 0 (zero). There will be two input files.

Output

For each n print μ(n) value on new line.

Example

Input:
1
2
3
4
5
6
0

Output:
1
-1
-1
0
-1
1


Added by:julkas
Date:2018-05-15
Time limit:60s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All