该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

This is about a game of fighting all the squrare numbers and prime numbers.

At the very beginning, $N$ people are sitting in $N$ seats, and the seats are numbered from 1 to $N$, from left to right. Then for all the seats with their numbers being squares (such as 1, 4, 9, 16, ...), those people sitting in must leave, and everyone else must shift toward left so that there is no empty seat between any of them. If there are more than one people left, the game continues, but instead of square numbers, this round will let everyone sitting in the prime seats leave, and then the rest of them will shift to fill the empty seats again.

The game continues with checking the square seats and prime seats alternatively, until there is only one winner left. You are supposed to tell the initial seat number for this winner.

输入格式

Each input file contains one test case, in which a positive integer $N$ ($\le 10^5$) is given.

输出格式

For each test case, print in a line the initial seat number for this winner.

样例

10

6

限制

对于所有的测试用例,限制为400 ms, 64 MB