Masala #0122

Azimjon tub qiymatlarni judayam yaxshi ko’radi. Agar natural son quyidagi shartlarni qanoatlantirsa Azimjon bu sonni sevimli son deb hisoblaydi:

• Sonning yozilishida barcha ketma-ket joylashgan 3 ta raqamlar yig’indisi tub bo’lishi shart:

• Sonning yozilishida barcha ketma-ket joylashgan 4 ta raqamlar yig’indisi tub bo’lishi shart:

• Sonning yozilishida barcha ketma-ket joylashgan 5 ta raqamlar yig’indisi tub bo’lishi shart:

Sizga T marotaba bir xil savol beriladi. Har bir savolda bitta N soni kiritiladi, siz N xonali natural sonlar ichida Azimjonning sevimli sonlari nechta ekanligini aniqlang. Bu son juda katta bo’lishi mumkin, shuning uchun sizdan faqatgina shu sonning 10⁹+7 ga bo’lgandagi qoldig’ini toppish talab qilinadi.

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 2×10⁴)  testlar soni kiritiladi. Keyingi T ta qatorda bittadan butun son, N(1 ≤ N ≤ 4×10⁵) soni kiritiladi.

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda N xonali Azimjonning sevimli sonlari sonini 10⁹+7 ga bo’lgandagi qoldiqni chop eting.