Power of Divisors

시간 제한1초메모리 제한2048 MB

요약

x가 10^18 이하로 주어질 때 n^f(n) = x를 만족하는 가장 작은 n을 구하거나, 없으면 -1을 출력한다. 여기서 f(n)은 n의 약수 개수다.

난이도: 보통10점 중 6점
유형: 정수론, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

Consider a positive integer $n$ . Let $f(n)$ be the number of positive integer divisors of $n$ . For example, if $n=8$ then $f(n)=4$ , since the divisors of $8$ are $1$ , $2$ , $4$ and $8$ .

Now, consider a positive integer $x$ . What is the smallest value of $n$ such that $n^{f(n)}=x$ ?

입력

The single line of input contains a single integer $x$ ( $1 \le x \le 10^{18}$ ). This is the $x$ of the statement above.

출력

Output a single integer, which is the smallest value of $n$ such that $n^{f(n)}=x$ , or $-1$ if no such value of $n$ exists.

예제3

예제 1
입력
```
15625
```
예상 출력
```
25
```
예제 2
입력
```
64000000
```
예상 출력
```
20
```
예제 3
입력
```
65536
```
예상 출력
```
-1
```