单点时限: 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)$ 。
6
2
9
9