E. Число по-русски
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Напишите программу для поиска такого наименьшего натурального (целого положительного) числа, что его запись на русском языке в именительном падеже содержит ровно $$$k$$$ символов без учёта пробелов.

Входные данные

Вводится одно целое число $$$k$$$ ($$$1 \le k \le 165$$$).

Выходные данные

Выведите искомое число. Если ответа не существует, выведите 0.

Система оценки

В данной задаче 100 тестов, за прохождение каждого теста даётся один балл.

Пример
Входные данные
150
Выходные данные
11488488484484
Примечание

Число в ответе из примера по-русски пишется так: «одиннадцать триллионов четыреста восемьдесят восемь миллиардов четыреста восемьдесят восемь миллионов четыреста восемьдесят четыре тысячи четыреста восемьдесят четыре». Эта строка содержит 150 символов без учёта пробелов.

В данной задаче предполагается, что для чисел, больших единицы, слово «один» или «одна» в начале числа не пишется, а не в начале — пишется. Например, число 1001001 запишется как «миллион одна тысяча один».

Участникам, пишущим на языке C++, не рекомендуется использовать в своей программе строковые константы на русском языке, поскольку функции length и strlen на сервере могут некорректно вычислять длину строк с русскими буквами (из-за кодировки Unicode).