// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define mod 1000000007
#define inf (int)1e18+5
#define sz(x) (int)x.size()
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
typedef long double ld;
typedef pair<int,int> pii;
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////
const int N=1e5+5;
int dp[65][2][8][2];
int n;
string s;
int solve(int ind,int lim,int prev,int found){
if(ind==n){
if(prev==5)
found=1;
return found;
}
int &ans=dp[ind][lim][prev][found];
if(ans!=-1)
return ans;
ans=0;
int nxt=0;
int d1=(prev&1),d2=(prev&2);
if(d1){
nxt|=2;
}
if(d2){
nxt|=4;
}
if(prev==5){
found=1;
}
if(lim){
int val=s[ind]-'0';
for(int i=0;i<=val;i++){
ans+=solve(ind+1,i==val,nxt|i,found);
}
}
else{
for(int i=0;i<=1;i++){
ans+=solve(ind+1,0,nxt|i,found);
}
}
return ans;
}
string DTOB(int x){
string ans;
for(int i=0;i<63;i++){
if(x&(1LL<<i))
ans+='1';
else
ans+='0';
}
while(sz(ans) && ans.back()=='0')
ans.pop_back();
if(ans.empty())
ans='0';
reverse(all(ans));
return ans;
}
int32_t main(){__
int te;
cin>>te;
while(te--){
int l,r;
cin>>l>>r; // least value of l should be 1.
l--;
memset(dp,-1,sizeof dp);
s=DTOB(l);
n=sz(s);
// debug()<< imie(s);
int val1=solve(0,1,0,0);
s=DTOB(r);
n=sz(s);
// debug()<< imie(s);
memset(dp,-1,sizeof dp);
int val2=solve(0,1,0,0);
cout<<val2-val1<<"\n";
}
return 0;
}
Ly8gI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKLy8gI3ByYWdtYSBHQ0MgdGFyZ2V0KCJzc2Usc3NlMixzc2UzLHNzc2UzLHNzZTQscG9wY250LGFibSxtbXgsYXZ4LHR1bmU9bmF0aXZlIikKLy8gI3ByYWdtYSBHQ0Mgb3B0aW1pemUoInVucm9sbC1sb29wcyIpCi8vICNwcmFnbWEgY29tbWVudChsaW5rZXIsICIvc3RhY2s6MjAwMDAwMDAwIikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zIikKI3ByYWdtYSBHQ0MgdGFyZ2V0ICgic3NlNCIpCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGludCBsb25nIGxvbmcKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwojZGVmaW5lIGluZiAoaW50KTFlMTgrNQojZGVmaW5lIHN6KHgpIChpbnQpeC5zaXplKCkKI2RlZmluZSBQSSAzLjE0MTU5MjY1MzU4OTc5MzIzODUxMAojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwoeCkuZW5kKCkKI2RlZmluZSByYWxsKHgpICh4KS5yYmVnaW4oKSwoeCkucmVuZCgpCiNkZWZpbmUgX18gaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7Y2luLnRpZSgwKTtjb3V0LnRpZSgwKTsKI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIHZwaWkgdmVjdG9yPHBhaXI8aW50LGludD4gPiAKI2RlZmluZSB2dmkgdmVjdG9yPHZlY3RvcjxpbnQ+ID4KI2RlZmluZSBQUklOVF9USU1FIGNlcnIgPDwgIlRpbWUgZWxhcHNlZDogIiA8PCAxLjAgKiBjbG9jaygpIC8gQ0xPQ0tTX1BFUl9TRUMgPDwgIiBzLiIgPDxlbmRsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIHBhaXI8aW50LGludD4gcGlpOwovLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCmNvbnN0IGludCBOPTFlNSs1OwppbnQgZHBbNjVdWzJdWzhdWzJdOwppbnQgbjsKc3RyaW5nIHM7CmludCBzb2x2ZShpbnQgaW5kLGludCBsaW0saW50IHByZXYsaW50IGZvdW5kKXsKICAgIGlmKGluZD09bil7CiAgICAgICAgaWYocHJldj09NSkKICAgICAgICAgICAgZm91bmQ9MTsKICAgICAgICByZXR1cm4gZm91bmQ7CiAgICB9CiAgICBpbnQgJmFucz1kcFtpbmRdW2xpbV1bcHJldl1bZm91bmRdOwogICAgaWYoYW5zIT0tMSkKICAgICAgICByZXR1cm4gYW5zOwogICAgYW5zPTA7CiAgICBpbnQgbnh0PTA7CiAgICBpbnQgZDE9KHByZXYmMSksZDI9KHByZXYmMik7CiAgICBpZihkMSl7CiAgICAgICAgbnh0fD0yOwogICAgfQogICAgaWYoZDIpewogICAgICAgIG54dHw9NDsKICAgIH0KICAgIGlmKHByZXY9PTUpewogICAgICAgIGZvdW5kPTE7CiAgICB9CiAgICBpZihsaW0pewogICAgICAgIGludCB2YWw9c1tpbmRdLScwJzsKICAgICAgICBmb3IoaW50IGk9MDtpPD12YWw7aSsrKXsKICAgICAgICAgICAgYW5zKz1zb2x2ZShpbmQrMSxpPT12YWwsbnh0fGksZm91bmQpOwogICAgICAgIH0KICAgIH0KICAgIGVsc2V7CiAgICAgICAgZm9yKGludCBpPTA7aTw9MTtpKyspewogICAgICAgICAgICBhbnMrPXNvbHZlKGluZCsxLDAsbnh0fGksZm91bmQpOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBhbnM7Cn0Kc3RyaW5nIERUT0IoaW50IHgpewogICAgc3RyaW5nIGFuczsKICAgIGZvcihpbnQgaT0wO2k8NjM7aSsrKXsKICAgICAgICBpZih4JigxTEw8PGkpKQogICAgICAgICAgICBhbnMrPScxJzsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGFucys9JzAnOwogICAgfQogICAgd2hpbGUoc3ooYW5zKSAmJiBhbnMuYmFjaygpPT0nMCcpCiAgICAgICAgYW5zLnBvcF9iYWNrKCk7CiAgICBpZihhbnMuZW1wdHkoKSkKICAgICAgICBhbnM9JzAnOwogICAgcmV2ZXJzZShhbGwoYW5zKSk7CiAgICByZXR1cm4gYW5zOwp9CmludDMyX3QgbWFpbigpe19fCiAgICBpbnQgdGU7CiAgICBjaW4+PnRlOwogICAgd2hpbGUodGUtLSl7CiAgICAgICAgaW50IGwscjsKICAgICAgICBjaW4+Pmw+PnI7IC8vIGxlYXN0IHZhbHVlIG9mIGwgc2hvdWxkIGJlIDEuCiAgICAgICAgbC0tOwogICAgICAgIG1lbXNldChkcCwtMSxzaXplb2YgZHApOwogICAgICAgIHM9RFRPQihsKTsKICAgICAgICBuPXN6KHMpOwogICAgICAgIC8vIGRlYnVnKCk8PCBpbWllKHMpOwogICAgICAgIGludCB2YWwxPXNvbHZlKDAsMSwwLDApOwogICAgICAgIHM9RFRPQihyKTsKICAgICAgICBuPXN6KHMpOwogICAgICAgIC8vIGRlYnVnKCk8PCBpbWllKHMpOwogICAgICAgIG1lbXNldChkcCwtMSxzaXplb2YgZHApOwogICAgICAgIGludCB2YWwyPXNvbHZlKDAsMSwwLDApOwogICAgICAgIGNvdXQ8PHZhbDItdmFsMTw8IlxuIjsKICAgIH0KcmV0dXJuIDA7Cn0=