Safe
----

Imagine a game where n players sit in a circle. An arbitrary player is
designated as player number 1. The player to their left is player number
2, the next player to the left is number 3 etc. 

The game proceeds as follows. Player 1 starts. They "remove" the player
to their left, i.e. player 2. Next, since player 2 is out, it is player
3's turn who "removes" player 4. Next, player 5 "removes" player 6 etc.
The game continues in this fashion, where the next remaining player
always removes the player to their left until only one player is left.
That player is said to be safe.

Your task is, given a positive integer n as input, to calculate the
"safe" position, i.e. the number of the player that will be safe at the
end of the game.

Input
-----

The input will be several non-negative integer values (each number on a
separate line) that are guaranteed to be less that 1,000,000.  The end
of the input will be indicated by a value of 0, which should not be
processed.

Output
------

For each input number, output the number of the safe position.

Sample Input
------------

5
123456
0

Sample Output
-------------

3
115841