3721. 完全平方数

单点时限: 1.0 sec

内存限制: 512 MB

QQ小方以前不会判断什么是完全平方数,现在他会了,所以他急切的想教会你。

如果一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。

即如果有整数 $x$ 存在 $x=y^2$ 且 $y$ 也是一个整数,那么这个数 $x$ 称为完全平方数。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

QQ小方刚学完离散数学,所以他定义了一个单射函数 $S(n)$ ,其中 $S(n)$ 是满足下述条件的最大正整数 $m$ :

存在递增的整数序列, $m=a_1<a_2<\cdots <a_t=n$ ,使得 $a_1\cdot a_2\cdot \cdots \cdot a_t$ 是一个完全平方数。

如果不存在这样的 $m$ ,我们令 $S(n)=-1$ 。

显然,如果 $n$ 是完全平方数,则 $t=1,n=m$ 。

现在QQ小方会告诉你 $n$,他需要你告诉他 $ S(n) $ 的值。

输入格式

输入包含一行一个数据 $n(1\le n\le 10^6)$ 。

输出格式

输出第一行包含一个整数表示 $S(n)$ 。

样例

Input
6
Output
2
Input
9
Output
9

10 人解决,186 人已尝试。

22 份提交通过,共有 811 份提交。

8.7 EMB 奖励。

创建: 1 年,2 月前.

修改: 1 年,2 月前.

最后提交: 10 月前.

来源: N/A

题目标签