제곱 인수를 가진 수

양의 정수 $k$가 $d > 1$인 모든 정수 $d$에 대해 $d^2$으로 나누어떨어지지 않을 때, $k$를 제곱 인수가 없는 수(squarefree)라고 합니다. 반대로 $d > 1$인 어떤 정수 $d$가 존재하여 $k$가 $d^2$으로 나누어떨어지면, $k$를 제곱 인수를 가진 수(non-squarefree)라고 합니다.

예를 들어 제곱 인수를 가진 수를 작은 것부터 나열하면 $4, 8, 9, 12, 16, \dots$ 입니다.

제곱 인수를 가진 수를 오름차순으로 나열했을 때 $n$번째 수를 출력하세요.

첫째 줄에 정수 $n$이 주어집니다. ($1 \le n \le 10^{10}$)

$n$번째 제곱 인수를 가진 수를 한 줄에 출력하세요.