#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;
ifstream f("fibocel.in");
ofstream g("fibocel.out");
long long comb[55][55];
long long int fib[50],nrtermeni;
void precalccomb()
{comb[0][0]=1;
    comb[1][1]=1;
    comb[1][0]=1;
    for(int i=2;i<=50;i++)
    {comb[i][0]=1;
        for(int j=1;j<=i;j++)
        {
            comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
        }
    }
}
void precalcfib()
{
    fib[1]=1;
    fib[2]=2;
    int p;
    for(int i=3;i<=30;i++)
    {
        p=fib[i-1]+fib[i-2];
        if(p>50) break;
        fib[i]=p;
        nrtermeni=i;
    }
}
long long int  fibocel(long long int x)
{bool bit[55];
    int nrbiti=0,biti1=0;

    long long cx=x;
    while(cx>0)
    {if(cx%2==1) biti1++;
     bit[++nrbiti]=cx%2;
     cx/=2;
    }


    long long sol=0;
    int copie1=biti1;
    for(int z=1;z<=nrtermeni;z++)
    {
        sol+=comb[nrbiti-1][fib[z]];
biti1=copie1;

        for(int i=1;i<nrbiti;i++)
        {
                if(bit[i]==1)
                {
                    biti1--;
                    if(fib[z]>=biti1){
                    sol+=comb[i-1][fib[z]-biti1];
                    }

                }


    }



    }



    return sol;

}
int main()
{
precalccomb();

precalcfib();

int q;
f>>q;
for(int i=1;i<=q;i++)
{
  long long   int a,b;
    f>>a>>b;
g<<fibocel(b+1)-fibocel(a)<<'\n';
}



}