Joseph

Time limit1sMemory limit128 MB

Summary

For each k, find the smallest step size m in the Josephus circle that kills all k bad people before any of the k good people.

Level: Medium5 of 10
Topics: Simulation, Implementation, Brute force, Math
Solved: No attempts yet

Problem

The Josephus problem is famous. For those unfamiliar with the original: $n$ people numbered $1, 2, \ldots, n$ stand in a circle, and every $m$ -th person is executed; only the last remaining person survives. Joseph was clever enough to choose the position of the last survivor, saving his own life so that he could later tell us about the incident. For example, when $n = 6$ and $m = 5$ , the people are executed in the order $5, 4, 6, 2, 3$ , and person $1$ survives.

Now suppose there are $k$ good people and $k$ bad people. In the circle the first $k$ are the good people and the last $k$ are the bad people. Determine the smallest $m$ such that every bad person is executed before the first good person.

Input

The input consists of several lines, each containing a single integer $k$ . The last line contains $0$ . You may assume that $0 < k < 14$ .

Output

For each $k$ in the input, print the corresponding $m$ on its own line.

Examples3

Example 1
Input
```
3
4
0
```
Expected output
```
5
30
```
Example 2
Input
```
1
0
```
Expected output
```
2
```
Example 3
Input
```
2
0
```
Expected output
```
7
```