The Josephs problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1, 2, . . . , n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.

 

The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the Composite numbers succession (4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, ...). So in order to kill the i-th person, Josephus cousin counts up to the i-th composite.

 

A composite number is a positive integer that has at least one positive divisor other than one or the number itself. In other words, a composite number is any integer greater than one that is not a prime number.

 

For example, there are 6 people in a circle, and the sequence of couting is composite number succession (4, 6, 8, 9, 10, …).

In the beginning, the step to kill m = 4. The sequence of killing people is as follows.

1, 2, 3, 4.............................(kill 4, and m is changed to 6)

5, 6, 1, 2, 3, 5.....................(kill 5, and m is changed to 8)

6, 1, 2, 3, 6, 1, 2, 3.............(kill 3, and m is changed to 9)

6, 1, 2, 6, 1, 2, 6, 1, 2.........(kill 2, and m is changed to 10)

6, 1, 6, 1, 6, 1, 6, 1, 6, 1.....(kill 1)

Each line with 1 integers, n. n is the number of people.Input terminated by EOF.

 

Testcase 1 : 1<=n<100

Testcase 2 : 100<=n<1000

Testcase 3 : 1000<=n<10000

Testcase 4 : 10000<=n<50000

Testcase 5 : 50000<=n<100000