Assistance Required

Time limit1sMemory limit128 MB

Summary

Generate lucky numbers by repeatedly removing every k-th remaining element, and report the n-th lucky number for each query.

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

Problem

After the 1997/1998 Southwestern European Regional Contest, held in Ulm, a large contest after-party took place. The organizing team invented a special way to choose the participants who would help wash the dirty dishes.

The contestants line up in a queue, one behind the other. Each contestant is given a number, starting with 2 for the first contestant, 3 for the second, 4 for the third, and so on, consecutively.

The first contestant in the queue is asked for his number, which is 2. He is freed from the washing up and can keep partying, but every second contestant behind him has to go to the kitchen (those with numbers 4, 6, 8, and so on). Then the next contestant in the remaining queue tells his number. He answers 3 and is freed, but every third contestant behind him is selected to help (those with numbers 9, 15, 21, and so on). The next contestant in the remaining queue has number 5 and is free, but every fifth contestant behind him is chosen (those with numbers 19, 35, 49, and so on). The next has number 7 and is free, but every seventh contestant behind him has to assist, and so on.

Let us call the number of a contestant who does not have to help with the washing up a lucky number. Continuing this selection scheme, the lucky numbers form the ordered sequence 2, 3, 5, 7, 11, 13, 17, and so on. Determine these lucky numbers for the next contest party.

Input

The input contains several test cases. Each test case consists of an integer $n$ , where $1 \le n \le 3000$ . A single $0$ follows the last test case to mark the end of the input.

Output

For each test case given by $n$ , output the $n$ -th lucky number on a single line.

Examples4

Example 1
Input
```
1
2
10
20
0
```
Expected output
```
2
3
29
83
```
Example 2
Input
```
1
0
```
Expected output
```
2
```

Example 3

Input

Expected output

Example 4
Input
```
3000
0
```
Expected output
```
33809
```