# Programming contests

## ECN programozó csapatverseny, 2017. május 13.

May 13, 2017 10:10 AM – May 13, 2017 3:10 PM

# 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`
1. `-1`
2. `0`
3. `-1`
4. `0`
5. `0`
6. `1`
7. `-1`
8. `1`