Müəmmalı ayin
Кратос sirli bir ritualın təsvir olunduğu bir kitab tapdı. Əvvəlcə istənilən n ədədini seçmək olar. Sonra onunla aşağıdakı əməliyyatları yerinə yetirmək lazımdır:
n ədədinin onluq yazılışında ən kiçik rəqəmi yadda saxla.
n tam olaraq 10-a bölünmədiyi müddətcə yadda saxlanılan rəqəmi n-ə əlavə et.
n-i 10-a böl və ritualın əvvəlinə qayıt.
Ritual sonsuz davam edir və kitabda yazılıb ki, bu ritual zamanı n-ə bərabər olan ən kiçik ədəd sehrli ədəddir. Кратос hələ hansı ilkin n-i seçəcəyinə qərar verməyib. Ona hər bir ilkin variant üçün uyğun sehrli ədədi müəyyən etməyə kömək edin.
Giriş məlumatları
Birinci sətirdə t testlərin sayı verilir (1 ≤ t ≤ 10^5). Növbəti t sətirdə testlər verilir. Hər bir test bir tam ədəd n[i] (1 ≤ n[i] < 10^500001) - i-ci testdə n-in ilkin dəyərini ehtiva edir. Bütün testlərdə ədədlərin ümumi uzunluğu 500000-i keçmir.
Çıxış məlumatları
Hər bir test üçün yeni sətirdə ritual zamanı n-ə bərabər olacaq ən kiçik ədədi çıxarın.