Masala #0971

Xotira 128 MB Vaqt 1000 ms
14

Sonlar o`qidagi girlyanda #2

Masalaning #1 va #2 versiyalari tubdan farq qiladi. Ularni alohida masalalar sifatida hisoblash to`g`riroqdir.

Yangi yilda arafasida, yangi yil ruhini bag`ishlovchi har xil bezak buyumlari mavjud. Asilbekka eng yoqgani - girlyandadir. Uni istalgan joyga ossa bo`ladi, devorga, mebelga, archaga... Asilbek esa girlyandani sonlar o`qiga osilganini ham ko`rgan!

Asilbek o`zining sevimli sonlar o`qining musbat tomoniga qarasa, u to`liq girlyanda bilan bezatilgan ekan. Bunda \(a\) va \(b(a \neq b)\) sonlar girlyanda bilan bog`langan, agarda \(a|b\) yoki \(b|a\) (bir sonni ikkinchisini qoldiqsiz bo`ladi) sharti qanoatlantirsa.

Payqash qiyin emaski, 1 sonidan girlyandalar orqali boshqa barcha sonlarga borish mumkin. Girlyanda orqali faqat katta songa o`tish mumkin bo`lsa, 1 sonidan \(A\) sonigacha eng ko`pi bilan nechta o`tish yordamida yetib olish mumkinligini oldin hisoblagan edik. Sizning endigi vazifangiz bunday o`tishlar sonini hisoblashdir.

Boshqa so`zlar bilan, 1 sonidan A sonigacha eng ko`p girlyandalar orqali o`tishning necha xil usuli mavjud?


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 2*10^5)\) testlar soni kiritiladi.

Keyingi  \(T\) ta qatorning har birida bittadan butun son - \(A(2 \leq A \leq 10^7)\) soni kiritiladi.


Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda bitta butun son, masala javobini chop eting.


Misollar
# input.txt output.txt
1
3
12
4
7
3
1
1
2
2
100
1
6
1
Izoh:

1-test:

12 ga yetib olish eng ko`pi bilan 3 ta girlyanda o`tishi orqali yetib borish mumkin. Bunday o`tishlar jami 3 xil.

1 -> 2 -> 4 -> 12

1 -> 2 -> 6 -> 12

1 -> 3 -> 6 -> 12