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

题目描述

"打掉平方素"是把平方数和素数逐个筛除的游戏。

游戏最开始有 $N$ 位玩家，从左到右坐在编号从 1 到 $N$ 的座位上。游戏开始后，首先坐在编号为平方数（例如 1、4、9、16、……）座位上的玩家出局，剩下的玩家向左边移动，使得任何两个玩家间没有空座位留下。大家坐定后，下一轮请坐在编号为素数座位上的玩家出局，剩下的玩家再次向左边移动。如此反复，交替筛除平方数和素数座位上的玩家，直到最后只有一个赢家剩下来。本题就请你给出这个赢家最初的座位号。

输入格式

输入给出一个正整数 $N$（$\le 10^5$）。

输出格式

在一行中输出这个游戏赢家最初的座位号。

样例

10

6

样例解释

第 1 轮：坐在 1、4、9 号座位的玩家离开。坐在编号为 1 到 7 的座位上的玩家们的初始座位号依次为 2、3、5、6、7、8、10。

第 2 轮：坐在 2、3、5、7 号座位的玩家离开。坐在编号为 1 到 3 的座位上的玩家们的初始座位号依次为 2、6、8。

第 3 轮：坐在 1 号座位的玩家离开。坐在编号为 1 到 2 的座位上的玩家们的初始座位号依次为 6、8。

第 4 轮：坐在 2 号座位的玩家离开。最后赢家的初始座位号为 6。

限制

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