题目描述

小 W 喜欢完全平方数，因此想选出一些正整数使得它们的乘积是完全平方数，并且他希望最大数最小。

小 W 随即发现 $\{1\}$ 满足条件，因此他规定这个集合中的最小数是 $n$，显然这样一定有解。然而他不想计算这么复杂的问题，所以把这个构造问题交给了你。

输入格式

一行一个正整数 $n$。

输出格式

一行一个正整数表示最大数的最小值。

样例

样例解释

前 7 个分别可以取 $\{1\},\{2,3,6\},\{3,6,8\},\{4\},\{5,8,10\},\{6,8,12\},\{12,15,20\}$。

数据范围

对于所有数据，$n\le5\times10^6$。有参数 $N_{1\dots5}$，对 $1\le i\le5$，若你通过所有 $n\le N_i$ 的测试点，你获得 20 分，其中 $N=[20,500,2\times10^4,1\times10^6,5\times10^6]$