Möbius Function

For any positive integer x, the classical Möbius function μ(x) has values in {–1, 0, 1}, defined in the following way:

μ(x) = 1 if x is a square-free positive integer with an even number of prime factors;
μ(x) = –1 if x is a square-free positive integer with an odd number of prime factors;
μ(x) = 0 if x has a squared prime factor.

Write a program that calculates the value of the Möbius function for a given positive integer.

Input Specification

The input contains several numbers, where each number is less than 2 000 000 000.

Output Specification

For each number, calculate the corresponding value of the Möbius function and write the result to the standard output, each value in a separate line.

Sample Input

1. 3
2. 4
3. 17
4. 48
5. 2727
6. 605700457
7. 1092678973
8. 1999999999

download as text file

Output for Sample Input

1. -1
2. 0
3. -1
4. 0
5. 0
6. 1
7. -1
8. 1

download as text file