Татьяна любит держать вещи в порядке. Ее игрушки отсортированы от самых маленьких до самых больших, ее карандаши отсортированы от самых коротких до самых длинных, а ее компьютеры - от самых старых до самых новых. Однажды, практикуя свои навыки подсчета, она заметила, что у некоторых целых чисел, когда они записаны в десятичной системе исчисления без ведущих нулей, их цифры отсортированы в неубывающем порядке. Некоторыми примерами этого являются 8, 123, 555 и 224488. Она решила назвать эти номера аккуратными. Номера, которые не имеют этого свойства, такие как 20, 321, 495 и 999990, не являются чистыми.

Она только что закончила считать все натуральные числа в порядке возрастания от 1 до n. Какое последнее чистое число она посчитала?

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

Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Далее следуют t строк. Каждая строка содержит одно целое число n (1 ≤ n ≤ 1018) - последнее число, которое посчитала Татьяна.

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

Для каждого теста выведите одну строку содержащую Case #x: y, где x - номер теста (начиная с 1), а y - последнее чистое число, которое посчитала Татьяна.