Masala #0122

Xotira 64 MB Vaqt 3000 ms
14

Azimjonning sevimli sonlari 2

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 109+7 ga bo’lgandagi qoldig’ini toppish talab qilinadi.


Kiruvchi ma'lumotlar:

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


Chiquvchi ma'lumotlar:

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


Misollar
# input.txt output.txt
1
1
6
95