Müəmmalı ayin

Kratos 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. Kratos 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.