Təmiz ədədlər

Татьяна əşyalarını səliqəli saxlamağı sevir. Onun oyuncaqları ən kiçikdən ən böyüyə, karandaşları ən qısadan ən uzuna, kompüterləri isə ən köhnədən ən yeniyə qədər sıralanır. Bir gün sayma bacarıqlarını təkmilləşdirərkən, bəzi tam ədədlərin, ondalık sistemdə ön sıfırlar olmadan yazıldığında, rəqəmlərinin artan qaydada sıralandığını gördü. Bu cür ədədlərə misal olaraq 8, 123, 555 və 224488 göstərilə bilər. O, bu ədədləri səliqəli adlandırmağa qərar verdi. 20, 321, 495 və 999990 kimi bu xüsusiyyətə malik olmayan ədədlər isə səliqəli deyil.

O, yalnız 1-dən n-ə qədər olan bütün təbii ədədləri artan qaydada saymağı bitirdi. O, hansı son səliqəli ədədi saydı?

Giriş məlumatları

Birinci sətir testlərin sayı t (1 ≤ t ≤ 100) verir. Sonrakı t sətir var. Hər sətir bir tam ədəd n (1 ≤ n ≤ 10^18) - Tatyana tərəfindən sayılan son ədəd.

Çıxış məlumatları

Hər test üçün Case #x: y formatında bir sətir çıxarın, burada x testin nömrəsidir (1-dən başlayaraq) və y Tatyana tərəfindən sayılan son səliqəli ədəddir.