E1 - Dvojité palindrómy 7DC

Možno si spomínate na minuloročnú úlohu o binárno-dekadických palindrómoch. Dlho sme rozmýšľali nad tým, prečo táto úloha mala takú nízku úspešnosť, až sme na to nakoniec prišli – ako správni programátori určite bežne nepočítate v takej zvláštnej, neprirodzenej sústave, ako je dekadická. Pripravili sme teda pre vás novú verziu úlohy, v ktorej sme túto zastaralú sústavu nahradili pre vás určite prirodzenejšou – hexadecimálnou (šestnástkovou).

Úloha

Dané sú čísla A a B. Zistite, koľko čísel z rozsahu A…B je takých, že ich binárny zápis aj ich hexadecimálny zápis (bez akýchkoľvek núl na začiatku) je palindróm.

Príkladom takéhoto čísla je (F090F)₁₆ = (11110000100100001111)₂.

Vstup

Prvý riadok vstupu obsahuje kladné celé číslo N určujúce počet testovacích sád. Každý z nasledujúcich N riadkov obsahuje dve medzerou oddelené kladné celé čísla A a B.

Výstup

Pre každú dvojicu čísel zo vstupu vypíšte jedno číslo – počet celých čísel x takých, že A ≤ x ≤ B a platí, že binárny aj hexadecimálny zápis čísla x je palindróm.

E1

1 ≤ N ≤ 10
1 ≤ A ≤ B < 100 000

E2

1 ≤ N ≤ 10 000
1 ≤ A ≤ B < 2⁶³

Príklad

Vstup:

3
1 100
42 47
1000 10000

Výstup:

9
0
18