Тетяна любить тримати речі в порядку. Її іграшки відсортовані від найменших до найбільших, її олівці відсортовані від найкоротших до найдовших, а її комп'ютери — від найстаріших до найновіших. Одного разу, практикуючи свої навички підрахунку, вона помітила, що деякі цілі числа, коли записані в десятковій системі числення без провідних нулів, мають цифри, відсортовані в неспадному порядку. Прикладами таких чисел є , , і . Вона вирішила назвати ці числа чистими. Числа, які не мають цієї властивості, такі як , , і , не є чистими.
Вона щойно закінчила рахувати всі натуральні числа в порядку зростання від до . Яке останнє чисте число вона підрахувала?
Перший рядок містить кількість тестів (1 \le t \le 100). Далі йдуть рядків. Кожен рядок містить одне ціле число (1 \le n \le 10^{18}) — останнє число, яке підрахувала Тетяна.
Для кожного тесту виведіть один рядок у форматі Case #x: y, де — номер тесту (починаючи з ), а — останнє чисте число, яке підрахувала Тетяна.
Приклад 1