XOR of GCDs

Given an integer \( n \), compute \( \bigoplus\limits_{i=1}^{n} \gcd(i, n) \), which is defined as:

\( \gcd(1,n) \oplus \gcd(2,n) \oplus \cdots \oplus \gcd(n,n), \)

Here, \( \gcd(a, b) \) denotes the greatest common divisor of \( a \) and \( b \), and \( \bigoplus \) denotes bitwise XOR (as in C++ using the ^ operator).

inputFormat

The input consists of a single integer \( n \) on one line.

outputFormat

Output a single integer representing \( \bigoplus\limits_{i=1}^{n} \gcd(i, n) \).

sample

1

1