완전제곱수가 되는 최소 배수

면접 대비

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

요약

n을 입력받아 n의 배수이면서 완전제곱수인 가장 작은 자연수를 출력합니다.

문제

자연수 $n$ 이 주어진다. $n$ 의 배수 중에서 어떤 자연수의 제곱(완전제곱수)이 되는 가장 작은 수를 구하여라.

첫째 줄에 자연수 $n$ 이 하나 주어진다 ( $1 \le n \le 500\,000\,000$ ).

첫째 줄에 $n$ 의 배수이면서 동시에 어떤 자연수의 제곱인 가장 작은 자연수 $m$ 을 출력한다.