你和朋友组建了一支“无调性打击乐手与大提琴手”乐队。你们在一起演奏了几年，但对目前的演奏水平感到不满足。在研究了一些有趣的新风格后，你被爵士乐世界中错综复杂的细节所吸引。

当然，你不可能立即应用所有学到的新东西，但你想从即兴创作一些美妙的新节奏型开始。你们将演奏一种节奏，每小节有 $n$ 拍，然后你将每一拍拆分为 $m$ 个音符。总共，每小节将有 $nm$ 个音符。

乐队里的每个人都知道，爵士乐中“没有平方的空间”（no room for squares）。因此，每小节的音符总数应该是无平方因子数（squarefree）。也就是说，不存在 $k > 1$ 使得 $k^2$ 整除每小节的音符总数。

打击乐手已经建议了每小节的拍数 $n$；现在轮到你找到一个每拍的音符数 $m$，使得它不会留下任何平方的空间。

在第二个样例中，我们有 $n = 30$ 且 $m = 7$。这是可行的，因为 $2 \le m < n$ 且 $m \times n = 210$ 没有除 $1$ 以外的平方因子。

输入格式

• 输入为一个无平方因子整数 $3 \le n \le 10^5$。

输出格式

• 输出一个整数 $2 \le m < n$，使得 $m \times n$ 仍然是无平方因子数。

如果有多个可能的解，你可以输出其中任意一个。

样例

样例输入 1

3

样例输出 1

2

样例输入 2

30

样例输出 2

7

样例输入 3

13

样例输出 3

10