J. Josephus Went Wrong
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You might have heard of the Josephus problem, where Josephus and $$$N - 1$$$ other soldiers arranged themselves in a circle and killed each other. Fast forward to the end, Josephus was the only person surviving. "Things would have been different if I proposed another rule," he thought.

Therefore, Josephus decided to time-travel back to 67 C.E. and proposed the following rule instead:

$$$N$$$ soldiers, including Josephus himself, arrange themselves in a circle. The soldiers are numbered from $$$1$$$ to $$$N$$$ clockwise. Soldier 1 holds two knives initially, one of which is labelled L (left) and the other is labelled R (right). The following process is then repeated:

  1. The soldier holding the knife L kills the soldier on his left. The soldier holding the knife R, who could possibly be the same soldier, simultaneously kills the soldier on his right.
  2. After that, the soldier holding the knife L, if still alive, passes the knife to the first alive soldier on his left. Simultaneously, the soldier holding the knife R, if still alive, passes the knife to the first alive soldier on his right.

The process ends when there is only one soldier alive, or when no alive soldiers are holding a knife. All the soldiers who are still alive will be surviving in the battle.

Josephus wants to find the number of surviving soldiers after this process. Can you help him?

Input

The first and only line of input consists of a single integer $$$N$$$ ($$$2 \leq N \leq 10^{18}$$$), the number of soldiers.

Output

Output a single integer: The number of surviving soldiers after this process.

Examples
Input
5
Output
1
Input
4
Output
1
Note

When $$$N = 5$$$, the process proceeds as follows:

  • Soldier 1 holds both knives L and R initially. He kills both soldiers 2 and 5, and passes the knives to soldiers 3 and 4 respectively.
  • Soldier 3 kills soldier 4 with his knife L and soldier 4 kills soldier 3 with his knife R simultaneously. Hence, both soldiers 3 and 4 are killed at the same time.
  • The process ends as all alive soldiers (i.e. soldier 1) are not holding a knife.

When $$$N = 4$$$, the process proceeds as follows:

  • Soldier 1 holds both knives L and R initially. He kills both soldiers 2 and 4, and passes both knives to soldier 3.
  • Soldier 3 kills soldier 1 with both his knives L and R.
  • The process ends as there is only one soldier alive.