8. Okná sa vymieňajú

Na matfyze sa v rámci prestavby začali vymieňať všetky okná. A to zahŕňa aj KSPácku miestnosť T2. A aby sme uvoľnili miesto robotníkom, musíme ju celú vypratať. Problém však je, že v T2 sa nachádza všetko. A tím myslím naozaj všetko. Od gitary, počítačov, hlavnovedúcovskej tyče, soba, masky Darth Vadera, cez chemikálie, terčovnicu, vŕtačku, papuče, po pílku na železo, hasiaci prístroj, TODO list a nič.¹ Naviac má každá z týchto vecí iný objem a keďže sa tu nachádza všetko, pre každé prirodzené číslo existuje v T2 jeden predmet s takýmto objemom.

Našťastie ako informatici máme dobrý komprimovací prístroj, ktorý dokáže bezstratovo zmenšiť objem ľubovoľného objektu s objemom väčším ako \(1\). Tento komprimátor funguje tak, že ak mal predmet pôvodne objem \(a\), po skomprimovaní bude mať tento predmet objem \(b\), kde \(b\) je počet jednotiek v binárnom zápise čísla \(a\). Ak sa napríklad \(a=19_{10}=10011_2\), tak \(b=3\). Teraz je snáď jasné, prečo sa predmet s objemom \(1\) nedá komprimovať. Táto komprimácia sa dá samozrejme opakovať, čím dostávame stále menšie a menšie predmety, až kým sa dostaneme na objem \(1\). Pre \(a=19\) musíme komprimáciu opakovať \(3\) krát, pričom dostanem postupne objemy \(3\), \(2\) a \(1\).

Avšak skôr ako sa komprimátor začal používať, nadšení a akciechtiví prváci vypratali časť T2 a zostali v nej len predmety, ktorých objemy sú medzi \(l\) a \(h\) vrátane. Všetky tieto predmety chceme teraz skomprimovať na objem \(1\), musíme si však dať pozor, aby sme ich vedeli dekomprimovať. Dôležité je, aby sme každý predmet dekomprimovali presne toľko krát, koľko krát sme ho komprimovali. Všetky veci (v tom čase už s objemom \(1\)) si teda uložíme do krabíc tak, aby veci, ktoré potrebovali rovnaký počet komprimácii, kým skončili s objemom \(1\), boli v tej istej krabici. Dopredu by sme však chceli vedieť, aké veľké krabice si máme pripraviť na ktorú sadu predmetov.

Úloha

Pre čísla \(l\), \(h\) a \(k\) určite počet takých predmetov s objemom medzi \(l\) a \(h\) vrátane, že na ich skomprimovanie na veľkosť \(1\) je potrebných práve \(k\) komprimácií.

Formát vstupu

Na prvom riadku vstupu je číslo \(t\) (\(1 \leq t \leq 1\,000\)) – počet vstupných testov.

Nasleduje \(t\) riadkov, každý obsahujúci tri čísla \(l\), \(h\) a \(k\) (\(2 \leq l \leq h \leq 10^{18}\), \(1 \leq k \leq 10^6\)).² \(l\) a \(h\) udávajú interval objemov, z ktorého vyberáme a \(k\) je žiadaný počet komprimácií.

Formát výstupu

Pre každý z \(t\) testov vypíšte jedno číslo – počet takých čísiel medzi \(l\) a \(h\), že sa skomprimujú na \(1\) po práve \(k\) komprimáciách.

Bodovanie

Vstupy sú rozdelené do \(10\) testovacích sád. Jednotlivé sady majú svoje obmedzenia a väčšinou platí, že vyriešiť skoršiu sadu je jednoduchšie. Zároveň by riešenia niektorých nižších sád mali pomáhať pri vymýšľaní zložitejších riešení.

• Pre sadu \(01\) platí, že \(t=100\), \(b\leq 10^6\), \(b-a \leq 1\,000\)
• Pre sadu \(02\) platí, že \(t=100\), \(b\leq 10^{18}\), \(b-a \leq 1\,000\)
• Pre sadu \(03\) a \(04\) platí, že \(t=1\,000\), \(b\leq 10^{18}\), \(b-a \leq 10^6\)
• Pre sadu \(05\) a \(06\) platí, že \(t=1\,000\), \(a=2\), \(b\leq 10^{18}\)
• Pre zvyšné sady neplatia žiadne špeciálne podmienky.

Príklad

Input:

2
4 11 2
4 11 3

Output:

4
2