지속성
시간 제한1초메모리 제한1024 MB
주어진 지속성 P에 대해, 각 자릿수를 곱하는 과정을 반복해 한 자리 수에 도달하는 횟수가 정확히 P인 가장 작은 음이 아닌 정수를 구한다.
문제
이전 문제에서 보았듯이, 심심할 때 엘리는 음이 아닌 정수 하나를 골라 자릿수로 나눈 뒤, 각 자릿수를 곱해 새로운 수를 얻는다. 예를 들어 42를 고르면 8을 얻고, 666을 고르면 216을 얻고, 1337을 고르면 63을 얻는다.
소녀는 고른 수의 결과에 같은 과정을 다시 적용할 수 있다는 것을 알아냈다. 예를 들어 1337에서 시작하면 63을 얻고, 여기에도 자릿수를 곱해 6 * 3 = 18을 얻는다. 한 단계 더 나아가 1 * 8 = 8을 얻을 수도 있다. 한 자리 수에 도달하면 더 할 것이 없으므로 소녀는 멈춘다.
엘리는 어떤 수의 "지속성"을 위 과정을 반복해 한 자리 수에 도달하는 데 필요한 반복 횟수라고 부른다. 예를 들어 3의 지속성은 0이고(이미 한 자리 수이다), 42의 지속성은 1이며(한 번 반복하면 8이 된다), 666과 1337의 지속성은 3이다(666 ⇒ 216 ⇒ 12 ⇒ 2, 1337 ⇒ 63 ⇒ 18 ⇒ 8).
문득 엘리는 주어진 지속성을 가지는 가장 작은 수가 무엇인지 궁금해졌다. 예를 들어 666과 1337의 지속성은 3이지만, 지속성이 3인 가장 작은 수는 39이다(39 ⇒ 27 ⇒ 14 ⇒ 4). 이제 소녀는 주어진 지속성 P를 가지는 가장 작은 수를 찾아 달라고 부탁한다.
입력
표준 입력의 한 줄에 정수 P가 주어진다. P는 엘리가 궁금해하는 지속성이다.
출력
표준 출력의 한 줄에 지속성이 P인 가장 작은 음이 아닌 정수를 출력한다.
제한
- 0 ≤ P ≤ 11
- 답이 1018보다 작음이 보장된다.
힌트
68889보다 작은 모든 자연수의 지속성은 6 이하다.