Given n persons, labeled by 1, 2, 3, ..., n in a circle, each surviving
person takes turn to kill some person, until only one person survives. The
rule is similar to the Josephus problem, where player 1 starts the
killing. The difference is that in the i-th turn, a player kills the i-th
person in front of him/her in the circle (where such a person could be
himself/herself). Also, after each killing, the one immediately after the
person being killed starts the killing in the next round. Our target is,
given the input n, output the label of the survivor.
Example:
Suppose n = 5. Beginning: 1 2 3 4 5 (in the circle)
Round 1: 1 3 4 5 (1 kills 2)
Round 2: 1 3 4 (3 kills 5)
Round 3: 3 4 (1 kills 1)
Round 4: 4 (3 kills 3)
==> Output 4 as the survivor.
Suppose n = 6. Beginning: 1 2 3 4 5 6 (in the circle)
Round 1: 1 3 4 5 6 (1 kills 2)
Round 2: 1 3 4 6 (3 kills 5)
Round 3: 1 3 6 (6 kills 4)
Round 4: 3 6 (6 kills 1)
Round 5: 3 (3 kills 6)
==> Output 3 as the survivor.
There are many cases in the input.
For each case, it is one line with n.
Input will end with EOF.
1410: n <= 30
1411: n <= 1000
1412: n <= 4000
For each case , output the label of the survivor.