Masala #0750

Tadqiqotchilarning hisob-kitoblariga ko’ra AQSH aholisining 10 foizi 13 sonidan qo’rqishadi, va har yilning 13-jumasini paraskevidekatriaphobia deb nomlashadi. Bu kun ular uchun 13 sonidanda qo’rqinchliroq hisoblanadi.

O’zimizning O’nuchboy ismli yigit yaqinda GreenCard da qatnashib Amerikaga yo’llanmani qo’lga kiritgan edi va u hozir Amerikada. O’nuchboy ismining ma’nosi sababli haligacha ish topolmayapti, chunki u hozirda ish izlab borgan joylarining barchasi ismining ma’nosini aytganidan so’ng ishga qabul qilmasliklarini aytishyabdi.

O’nuchboy ma’lumotlar bazasi bilan ishlaydigan firmalardan biriga ish izlab borganida ham xuddi shu holat takrorlandi. O’nuchboy buning sababini so’raganida ish beruvchi 13 raqamidan qo’rqishini aytdi. Shunda O’nuchboy ish beruvchiga 13 raqamidan qo’rqmaslik uchun shunchaki 13 sonini hech qayerda ishlatmaslikni taklif qildi. Bu taklifdan so’ng ish beruvchi O’nuchboyga «Taklifing zo’r. Hozirda meni ma’lumotlar bazamda id raqami 0 dan \(10^N-1\) gacha bo’lgan ma’lumotlar mavjud, shularni ichidan id raqami yozilishida 13 raqami mavjud bo’lgan barcha ma’lumotlarni o’chirsam bazamda jami nechta ma’lumot qolishini hisoblab bera olsang ishga qabul qilaman» deb vada berdi.

O’nuchboy matematikani yaxshi bilmaydi, ammo unga ish juda zarur, ishga kirishi uchun unga sizning yordamingiz kerak. O’nuchboyning ishga kirishida yordam bering.

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 10000)\) testlar soni kiritiladi. Keyingi \(T\) ta qatorda bittadan butun son, \(N (0 \le N \le 10^9+9)\) soni kiritiladi.

Chiqish faylida har bir test uchun alohida qatorda O’nuchboy topishi kerak bo’lgan sonni \(10^9+9\) ga bo’lgandagi qoldiqni chop eting.