Photons have a unique property called "polarization" that determines how they orient themselves, but what about eggs? Bobo the chicken has just placed some eggs in the incubator and wants to know which ones are oriented vertically. To solve this problem, she invents a special machine that can measure the "polarization" of eggs.
When Bobo presses a button, the solid floor of the incubator shifts, revealing a set of egg-shaped holes. These holes are shaped to allow only eggs that are facing upwards to fall through into a (soft) nest below. Eggs that aren't correctly oriented will remain on the solid parts of the floor.
Each egg can start in one of six possible orientations: horizontal, vertical, diagonal, anti-diagonal, right, and left. We label these orientations as "states" from 0 to 5 respectively. The first egg is always vertical, denoted by $$$X_1 := 1$$$, and the state of the $$$(n+1)^{\text{th}}$$$ egg (for $$$n \geq 1$$$) is represented by $$$X_{n+1} := ((4 \cdot X_{n}) \oplus n)\: \text{mod} \: 6$$$, where $$$\oplus$$$ is the XOR operator. Can you help Bobo figure out how many vertical-facing eggs are in the incubator?
The first line contains an integer $$$x\ \left(0 \lt x \leq 10^3\right)$$$ — the number of eggs in the incubator.
Please output the number of vertical-facing eggs in the incubator.
4
2
In the sample test case, the states of the first four eggs are 1, 5, 4, 1. Thus, egg #1 and egg #4 are facing upwards, so the answer is 2.
| Name |
|---|


