403552: GYM101193 C Crime fiction society

The society of crime fiction lovers holds meetings every day since September 13, 1842. Each day a member of the society with the membership card number x gives a talk. After more than 150 years the society chairmen collected enormous data about presenters, and it was decided to analyze it. Turns out, on the first society meeting a talk was given by the member number 1, on the second meeting spoke the member number 2, on the third day – 4, on the fourth day – 6, on the fifth day – 3 and so on. The chairman noticed, that each day the membership card number of the presenter is equal to the minimal positive integer number that is not coprime with the membership card number of the previous presenter and is not equal to membership numbers of those who gave talks before.

According to the tradition the card numbers of presenters were posted on the notice board, but in the Information Age the board was replaced with a digital screen. The society has bought software which computes the membership card number of the presenter on day n. However, the computation algorithm is very complex, so the society members is having doubts in its correctness. Could you please help them?

The only input line contains a single integer number n, which is the number of the day for which you need to determine the presenter.

Output the card number of the member who gives a talk on the n-th day.

35

42