题目描述

飞飞正在学习乘法和因数，若一个数x可以被分解为a*b，即x=a×b，那么我们就称a,b为x的因数，若a还是一个质数，则可以称a为x的质因数.飞飞在学习的过程中突然想到，每个大于1的数都可以被分解为若干个质因数相乘（若它本身是质数，那这个数就是自己的质因数），即每个大于1的数x都可以被分解为 的形式，其中pi为x的第i大的质因数，ti为pi在 x中的次数现在好奇的飞飞想要请你帮他找出，在给定x的所有质因数中，次数最高的数pi是多少，若有多个次数最高的质因数，则找到他们中最大的质因数pi.

输入格式

输入一个整数x

输出格式

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

300

5

数据规模与约定

对于30%的数据，x<=1000 对于60%的数据，x<=10000 对于100%的数据,1<x<=1000000

样例解释： 在所有的质因数中，5和2的次数最高，都为2，但是5>2 ，故飞飞想知道的答案是5.