마법의 성장 씨앗

마법의 씨앗은 크기가 1에서 시작하여 매일 2 이상 9 이하의 정수 배율로 성장한다. 즉, 현재 크기가 x일 때 다음 날의 크기는 x * f가 되며, f는 2 이상 9 이하의 정수이다. 이 과정을 원하는 횟수만큼 반복할 수 있다.

목표 크기 D 이하의 가장 큰 크기를 달성하고 싶다. 성장을 전혀 하지 않으면 크기는 1로 유지된다. 단, 결과가 1이면 성장에 실패한 것으로 간주하여 -1을 출력한다.

목표 크기 D가 주어질 때, 달성 가능한 가장 큰 크기를 구하시오.

입력

첫째 줄에 정수 D가 주어진다. (2 <= D <= 10^8)

출력

달성 가능한 D 이하의 최대 크기를 출력한다. 달성 불가능한 경우(결과가 1뿐인 경우) -1을 출력한다.

입출력 예시

입력 1

10

출력 1

10

입력 2

11

출력 2

10