#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

#include <iostream>

#include <queue>

#include <stack>

#include <vector>

#include <map>

#include <set>

#include <string>

#include <math.h>

using namespace std;

#pragma warning(disable:4996)

#pragma comment(linker, "/STACK:1024000000,1024000000")

typedef  long long LL;

const int INF = <<;

/*

*/

int num[];

LL dp[][];

int getNum(int sta)

{

    int tmp1, tmp2;

    for (int i = ; i <= ; ++i)

    {

        tmp1 = i &;

        tmp2 = sta % ;

        if (tmp1== && tmp2==)//偶数出现了偶数次

            return ;

        if (tmp1 ==  && tmp2 == )//奇数出现了奇数次

            return ;

        sta /= ;

    }

    return ;

}

int getSta(int x, int sta)

{

    int val = ;

    int newSta = sta;

    for (int i = ; i < x; ++i)

    {

        val *= ;

        sta /= ;

    }

    int times = sta % ;

    if (times ==  || times == )

        return newSta + val;

    else

        return newSta -  val;

}

LL dfs(int pos, int sta, bool zero, bool flag)

{

    if (pos == ) return getNum(sta);

    if (!flag && dp[pos][sta] != -) return dp[pos][sta];

    int end = flag ?  num[pos] : ;

    LL ans = ;

    for (int i = ; i <= end; ++i)

        ans += dfs(pos - , (zero&&i==)?:getSta(i, sta),zero&&i== ,flag&&i == end);

    if (!flag)

        dp[pos][sta] = ans;

    return ans;

}

LL calc(LL n)

{

    int len = ;

    while (n)

    {

        num[++len] = n % ;

        n /= ;

    }

    return dfs(len, , true, true);

}

int main()

{

    memset(dp, -, sizeof(dp));

    int t;

    LL l, r;

    scanf("%d", &t);

    while (t--)

    {

        scanf("%lld%lld", &l, &r);

        printf("%lld\n", calc(r) - calc(l - ));

    }

    return ;

}