제곱으로 나누어지지 않는 수

양의 정수 N이 1보다 큰 어떤 제곱수로도 나누어떨어지지 않으면, N을 제곱으로 나누어지지 않는 수라고 한다. 예를 들어 4, 9, 16, 25는 제곱수이고, 1, 2, 3, 5, 6, 7, 10, 11, 13, ...은 1보다 큰 제곱수로 나누어떨어지지 않는다.

K가 주어질 때, 오름차순으로 나열한 제곱으로 나누어지지 않는 수 중 K번째 수를 구하시오.

첫째 줄에 정수 K가 주어진다.

첫째 줄에 K번째 제곱으로 나누어지지 않는 수를 출력한다.

• 1 ≤ K ≤ 1,000,000,000