폴라드 로 인수분해

문제

양의 정수 $N$이 주어진다. $N$의 소인수 중 가장 큰 값을 구하라.

소인수분해 알고리즘으로 폴라드 로(Pollard's rho) 알고리즘을 쓰라.

입력

첫째 줄에 양의 정수 $N$이 주어진다.

• $2 \le N \le 10^{18}$

출력

$N$의 가장 큰 소인수를 출력하라.

예제 입력 1

12

예제 출력 1

3

예제 입력 2

1000000007

예제 출력 2

1000000007