fibocel

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#define infile "fibocel.in"
#define outfile "fibocel.out"
#define fMax 131
#define ll long long
using namespace std;
ll pas[fMax][fMax];
vector <int> fibo;

void initiFibo()
{
    fibo.push_back(1);
    fibo.push_back(2);

    for (int i = 2; fibo[i-1] + fibo[i-2] < fMax; ++i)
        fibo.push_back(fibo[i-1] + fibo[i-2]);
}

void initPascal()
{
    pas[0][0] = 1;

    for (int i = 1; i < fMax; ++i)
        for (int j = 0; j < i+1; ++j)
            pas[i][j] = pas[i-1][j-1] + pas[i-1][j];
}

string binary(ll x)
{
    if (!x)
        return "0";
    string ret = "";
    while (x)
    {
        int bit = x&1;
        x >>= 1;
        ret = char('0' + bit) + ret;
    }

    return ret;
}

ll query(ll x)
{
    string bin = binary(x);
    int l = bin.length();
    ll ret = 0;

    for (size_t f = 0; f < fibo.size() && fibo[f] <= l; ++f)
    {
        int neededBits = fibo[f];
        for (int i = 0; i < l; ++i)
        {
            int remainLength = l - i - 1;

            if (bin[i] == '1')
            {
                if (!neededBits)
                {
                    ret++;
                    break;
                }

                ret += pas[remainLength][neededBits];
                neededBits--;
            }
        }
    }
    return ret;
}

int main()
{
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
    initiFibo();
    initPascal();
    int q;
    scanf("%d", &q);
    while (q--)
    {
        ll x, y;
        scanf("%lld %lld", &x, &y);
        printf("%lld\n", query(y+1) - query(x));
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}