УСТОЙЧИВОСТ

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

요약

주어진 P에 대해 곱셈적 지속성(한 자리 수가 될 때까지 자릿수를 곱하는 반복 횟수)이 P인 가장 작은 음이 아닌 정수를 구한다.

난이도: 보통10점 중 4점
유형: 완전 탐색, 구현, 수학
정답자: 아직 제출이 없습니다

문제

Както може би знаете от предни задачи, когато скучае, Ели взима някакво неотрицателно цяло число, разбива го на цифри, умножава цифрите и получава ново такова число. Например, избирайки 42, тя получава 8, избирайки 666 тя получава 216, и избирайки 1337 тя получава 63.

Момичето забеляза, че може да направи същото върху резултата от числото, което е избрала, Например, започвайки с 1337, тя получава 63, на което също може да умножи цифрите, получавайки 6 * 3 = 18. Тя може да продължи дори още, получавайки 1 * 8 = 8. Когато стигне до едноцифрено число, момичето спира, тъй като няма какво повече да направи.

Ели нарича „устойчивост“ на числото броя на итерациите за прилагане на горната процедура, необходими за да се достигне до едноцифрено число. Например, устойчивостта на 3 е нула (то вече е едноцифрено), устойчивостта на 42 е 1 (след една итерация то става 8), а устойчивостта на 666 и 1337 е 3 (666 ⇒ 216 ⇒ 12 ⇒ 2 и 1337 ⇒ 63 ⇒ 18 ⇒ 8).

Изведнъж Ели се зачуди кое е най-малкото число с дадена устойчивост? Например, макар и 666 и 1337 да имат устойчивост 3, най-малкото число с тази устойчивост всъщност е едва 39 (39 ⇒ 27 ⇒ 14 ⇒ 4). Сега момичето ви моли да намерите най-малкото число, имащо дадена устойчивост P.

입력

На единствен ред на стандартния вход ще бъде зададено едно цяло число P – устойчивостта, която интересува Ели.

출력

На единствен ред на стандартния изход изведете едно неотрицателно цяло число – минималното, което има устойчивост P.

제한

0 ≤ P ≤ 11
Гарантирано е, че отговорът ще е по-малък от 1018.

힌트

Всички естествени числа, по-малки от 68889, имат устойчивост 6 или по-малка.

예제3

예제 1
입력
```
0
```
예상 출력
```
0
```
예제 2
입력
```
3
```
예상 출력
```
39
```
예제 3
입력
```
7
```
예상 출력
```
68889
```