Once upon a time, a king and a few of his soldiers were caught by an enemy king in a war.

He puts them in a circle. The first man in the circle has to kill the second man, the third man has to kill the fourth, fifth man to kill the sixth and so on. When the circle is completed, the remaining people have to form a circle and the process has to repeat. The last man standing will be set free.

If the king has to be set free, which position must he take? For any given N number of people, write a program to find the position that the king has to take.

Input
Any positive integer in the range 1 to 10000.

Output
A positive integer indicating safest position

Example

Input:
9

Output:
3

见题面

见题面