D2 - Bláznivý profesor

Spomínate si na bláznivú matematikárku Moniku? Našťastie sa už blížia maturitné skúšky, a tak (s trochou šťastia) Moniku už čoskoro stretnete naposledy. No, netešte sa predčasne – veď aj na vysokej škole sa môžete stretnúť s učiteľmi, ako je napríklad profesor Lordney, ktorý má na prestížnej univerzite South Jersey Private University sériu prednášok o algoritmoch. Profesor Lordney je medzi svojimi študentmi veľmi neobľúbený – jeho prednášky sú totiž plné chýb a otázky študentov sa často namiesto odpovede stretnú len s pobúreným mumlaním alebo vyhrážkami. Študenti, ktorí si uňho zapísali túto sériu prednášok, tak teraz musia tráviť dlhé hodiny rozmýšľaním o tom, ako opraviť nefunkčné algoritmy z profesorových prednášok.

Našťastie študenti aspoň vedia, že na skúške sa profesor takmer určite bude pýtať na svoj obľúbený algoritmus. Ako sa však dalo čakať, verzia z prednášky nefunguje, a keďže sami si s ním rady nevedia, ich poslednou šancou je, že im s týmto algoritmom pomôžete.

Úloha

Profesor Lordney má rád čísla, ktoré obsahujú len jeho dve obľúbené cifry – 4 a 8 (páčia sa mu napríklad čísla 8, 444 alebo 88484). Nie je teda prekvapením, že jeho obľúbeným je práve algoritmus, ktorý spočíta, koľko takýchto čísel sa nachádza v zadanom intervale ⟨A, B⟩.

Vstup

Na prvom riadku vstupu je počet intervalov P (1 ≤ P ≤ 100). Každý z nasledujúcich P riadkov obsahuje dve kladné celé čisla A a B – hranice jedného intervalu.

D1

1 ≤ A ≤ B ≤ 100 000

(pre študentov, ktorí boli na prednáškach ticho – alebo (v najlepšom prípade) sa na nich ani nezúčastňovali)

D2

1 ≤ A ≤ B ≤ 10⁵⁰

(pre študentov, ktorí mali na prednáškach príliš veľa otázok)

Výstup

Pre každý interval zo vstupu vypíšte jeden riadok obsahujúci jedinú hodnotu – počet čísel pozostávajúcich len z cifier 4 a 8, ktoré sa nachádzajú medzi číslami A a B (vrátane).

Príklad

Vstup:

4
4 8
1 100
100 200
75000 100000

Výstup:

2
6
0
16