题目描述

飞飞正在学习乘法和因数。若一个数 $x$ 可以被分解为 $x = a \times b$，则称 $a,b$ 为 $x$ 的因数；若 $a$ 还是质数，则称 $a$ 为 $x$ 的质因数。

飞飞在学习的过程中想到，每个大于 $1$ 的数都可以被分解为若干个质因数相乘的形式（若本身是质数，则其质因数就是它自己），即 $x = p_1^{t_1} \times p_2^{t_2} \times \dots \times p_k^{t_k}$，其中 $p_i$ 为 $x$ 的质因数（通常从大到小排列），$t_i$ 为对应质因数的次数。

现在飞飞想请你帮忙找出，在给定 $x$ 的所有质因数中，出现次数最高的 $p_i$ 是多少。若有多个次数最高的质因数，则输出其中最大的一个。

输入格式

一行，一个整数 $x$。

输出格式

输出一个整数，表示次数最高且本身最大的质因数。

样例

300

5

样例解释

$300 = 2^2 \times 3 \times 5^2$。质因数 $2$ 和 $5$ 的次数都是 $2$，均为最高，而 $5 > 2$，所以答案是 $5$。

数据范围

• 对于 $30\%$ 的数据：$x \le 1000$；
• 对于 $60\%$ 的数据：$x \le 10000$；
• 对于 $100\%$ 的数据：$1 < x \le 10^6$。