100000003 - largest prime factor

100000003 - largest prime factor

Time Limit

10 毫秒

Memory Limit

128 MB

通过次数

2

提交次数

5

旧版界面

$n$ 最大的质因数是多少？

Input

一个整数 $n$ 。

测试点1：n=600851475143

测试点2：n=939249648014412735

测试点3：n=281474976710656

Output

Examples

Input

Output

Hint

单个数字求质因数直接用短除法计算即可（对单组数据而言，打质数表得不偿失），但也有一些小技巧，例如从3开始所测试的被除数每次+2。