Чисті числа#8692

Чисті числа

1 секунда
128 мегабайтів
Легка

Тетяна любить тримати речі в порядку. Її іграшки відсортовані від найменших до найбільших, її олівці відсортовані від найкоротших до найдовших, а її комп'ютери — від найстаріших до найновіших. Одного разу, практикуючи свої навички підрахунку, вона помітила, що деякі цілі числа, коли записані в десятковій системі числення без провідних нулів, мають цифри, відсортовані в неспадному порядку. Прикладами таких чисел є , , і . Вона вирішила назвати ці числа чистими. Числа, які не мають цієї властивості, такі як , , і , не є чистими.

Вона щойно закінчила рахувати всі натуральні числа в порядку зростання від до . Яке останнє чисте число вона підрахувала?

Вхідні дані

Перший рядок містить кількість тестів (1 \le t \le 100). Далі йдуть рядків. Кожен рядок містить одне ціле число (1 \le n \le 10^{18}) — останнє число, яке підрахувала Тетяна.

Вихідні дані

Для кожного тесту виведіть один рядок у форматі Case #x: y, де — номер тесту (починаючи з ), а — останнє чисте число, яке підрахувала Тетяна.

Приклади

Приклад 1

Loading
Loading