수학은 재밌어

오일러는 수학을 정말 좋아해서 하루 종일 수학 공부만 하는 수학쟁이이다.

어느 날 오일러는 수학 공부를 하기 위해서 수학 책을 읽고 있던 중에 오일러 피 함수에 대해서 설명하는 부분을 보게 되었다. 오일러 피 함수는 다음과 같이 설명이 되어 있었다.

오일러 피 함수란 $\varphi(n)$으로 표기하며 1부터 $n$까지의 양의 정수 중에서 $n$과 서로소인 수의 개수를 나타내는 함수이다.

예를 들면 $\varphi(6)$은 1부터 6까지의 수 중 6과 서로소인 수의 개수를 말하는데 이는 1과 5로 두 개가 있으므로 $\varphi(6) = 2$이다.

오일러는 책의 내용을 곰곰이 읽던 중 어떤 문제가 떠올랐다. 문제의 내용은 다음과 같다.

어떤 양의 정수 $n$이 있다고 할 때, $x\varphi(x) = n$을 만족하는 양의 정수 $x$가 존재하는가?

고민에 빠진 오일러를 본 당신은 오일러의 궁금증을 해결해주기 위해서 직접 문제를 풀기로 결심했다. 그러므로 당신은 $x\varphi(x) = n$을 만족하는 $x$를 구하는 프로그램을 작성하면 된다.

첫 번째 줄에 $n$이 입력으로 주어진다. ($1 \le n \le 10^9$)

$x\varphi(x) = n$을 만족하는 양의 정수 $x$가 존재하면 최소의 $x$를, 존재하지 않으면 $-1$을 출력한다.