题目内容

有 $n$ 个人围坐成一个圆圈，从 $1$ 开始依次报数。每当有人报出的数字为一个“纯净数”时，该人就被淘汰并离开圆圈；下一个人继续从下一个数字报数，直到只剩一人。

定义：大于 $1$ 的整数，若只能被 $1$ 和自身整除，则称为纯净数。

请计算最后留下来的人在初始圆圈中的编号（编号从 $1$ 开始）。

约束：$1 \le n \le 10^4$。

输入描述

输入包含一行，一个整数 $n$，表示初始人数。

输出描述

输出一个整数，表示最终留下的人的初始编号。

样例1

输入

1

输出

1

说明

当只有 1 个人时，不需要进行任何淘汰，这个人直接留到最后。因此最终留下的编号就是 1。

样例2

输入

3

输出

1

说明

初始圆圈中有 3 个人，编号依次为 1、2、3。 报数过程：

• 第 1 个人报 1，1 不是纯净数，安全；
• 第 2 个人报 2，2 是纯净数，因此编号 2 被淘汰，剩余 1、3；
• 从编号 3 开始继续报下一个数字 3，3 是纯净数，编号 3 被淘汰，只剩编号 1。 最终留下的人是编号 1。

样例3

输入

4

输出

4

说明

初始圆圈有 4 个人，编号依次为 1、2、3、4。 报数过程：

• 编号 1 报 1，安全；
• 编号 2 报 2（纯净数），淘汰编号 2，剩余 1、3、4；
• 从编号 3 继续报 3（纯净数），淘汰编号 3，剩余 1、4；
• 从编号 4 继续报 4，不是纯净数；
• 接着编号 1 报 5（纯净数），淘汰编号 1，只剩编号 4。 最终留下的人是编号 4。

样例4

输入

5

输出

1

说明

初始圆圈有 5 个人，编号 1 到 5。 逐步淘汰过程：

• 报 2 时淘汰编号 2；
• 报 3 时淘汰编号 3；
• 报 5 时淘汰编号 5；
• 报 7 时淘汰编号 4。 此时仅剩编号 1，因此最终留下的是编号 1。 整个报数序列中的纯净数依次为 $2, 3, 5, 7$，每次被纯净数命中的玩家依次离开，最后剩下的是起点的 1 号。