XOR of Special Function Series

Define the function \(f(n)\) as follows:

\[ f(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}\Bigl[\operatorname{popcount}(i+j)\;\gcd(i,j)=\max(i,j)\Bigr], \]

where \(\operatorname{popcount}(x)\) denotes the number of ones in the binary representation of \(x\), and \(\gcd(i,j)\) is the greatest common divisor of \(i\) and \(j\). The bracket \([P]\) is an indicator function, which equals 1 if the property \(P\) is true and 0 otherwise.

It can be shown that the only pairs \((i,j)\) contributing to \(f(n)\) are of the following two types:

• Diagonal pairs: \(i=j\) such that \(\operatorname{popcount}(2i)=1\). Since \(\operatorname{popcount}(2i)=\operatorname{popcount}(i)\), this condition holds if and only if \(i\) is a power of 2.
• Off-diagonal pairs: Without loss of generality, assume \(i<j\). Write \(i=d\) and \(j=2d\) (this is necessary for \(\gcd(i,j)=d\) and \(\max(i,j)=2d\)). In this case the condition reduces to \[ \operatorname{popcount}(3d)=2. \] Both \((d,2d)\) and its symmetric pair \((2d,d)\) are counted.

Thus, for any positive integer \(n\), we have

[ f(n)=#{ i;:;1\le i\le n,, i \text{ is a power of }2} + 2\times #\Bigl{d;:;1\le d\le \lfloor n/2\rfloor,; \operatorname{popcount}(3d)=2\Bigr}. ]

Your task is: Given a positive integer \(n\), compute the value of

[ F(n)=f(1)\oplus f(2)\oplus\cdots\oplus f(n), ]

where (\oplus) denotes the bitwise XOR operation.

inputFormat

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

outputFormat

Output a single integer: the value of \(f(1)\oplus f(2)\oplus\cdots\oplus f(n)\).

sample

1

1