You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

求 $N$ 的第二大质因数。如果 $N$ 的质因数不足 $2$ 个，输出 $-1$。

比如 $N=150$，它的质因数有 $\{2,3,5\}$ 三个，其中第二大的是 $3$。

格式

输入格式

第一行包含一个整数 $N$。

输出格式

输出一个整数表示 $N$ 的第二大质因数。如果 $N$ 的质因数不足 $2$ 个，输出 $-1$。

样例

样例输入 #1

150

样例输出 #1

3

样例输入 #2

8

样例输出 #2

-1

样例输入 #3

330

样例输出 #3

5

数据规模

对于 $100\%$ 的数据，$2\leq N\leq 10^6$。