24307번 - УСТОЙЧИВОСТ 다국어

Както може би знаете от предни задачи, когато скучае, Ели взима някакво неотрицателно цяло число, разбива го на цифри, умножава цифрите и получава ново такова число. Например, избирайки 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
• Гарантирано е, че отговорът ще е по-малък от 10¹⁸.

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