Number Sequence III

Time Limit: 1 Second    Memory Limit: 32768 KB

Given number n, write number from 1 to n on the blackboard, then you get a number, let's call it n1. For example, given 11, we get n1=1234567891011. Then erase in n1 the numbers in the even positions, we get a new number n2(=1357901 in the former example). Next step, erase in n2 the numbers in the odd positions, we get n3(=370 in the former example). Then do the two steps above again and again, until there is only one number on the blackboard, print it.

Input

The input contains multiple test cases, each testcase contains only one number, n(1<=n<=99999). The input is ended by EOF.

Output

For each test case, print one number, the number left on the blackboard when the action descripted above done.

Sample Input

1
4

Sample Output

1
3

Submit

Source: ZOJ Monthly, December 2004