Prime Factor XOR

Given a positive integer \(n\), it is uniquely factorized as \(n = p_1 \times p_2 \times \dots \times p_k\), where each \(p_i\) is a prime and \(p_i \leq p_{i+1}\) for \(1 \leq i < k\). Your task is to compute the bitwise XOR of the sequence of prime factors, i.e., compute \(p_1 \oplus p_2 \oplus \dots \oplus p_k\).

Note: The bitwise XOR (denoted by \(\oplus\)) of a sequence of numbers is defined as the result obtained when all numbers are XORed together.

inputFormat

The input consists of a single line containing a positive integer n.

\(1 \leq n \leq 10^{12}\) (assumed constraint for efficient factorization).

outputFormat

Output a single integer, the bitwise XOR of all prime factors of n.

sample

6

1