#include <bits/stdc++.h>
 
#define ll long long
#define db double
 
#define pii pair<int, int>
 
#define vi vector<int>
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)
 
//pairs
#define fs first
#define se second
 
//vectors
#define pb push_back
#define pf push_front
 
//loops
#define FOR(i, a, b) for(int i=(int)a;i<=(int)b;++i)
#define ROF(i, a, b) for(int i=(int)a;i>=(int)b;i--)
#define rep(a, x) for(auto& a : x)
#define cc '\n'
 
//file
#define file(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
 
using namespace std;
 
const int maxn = 5*1e3+7;
const ll INF = 1e6;
 
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ll F[INF+1];
ll s[7] = {2,3,5,7,11,13,17};
map <ll, vector<ll>>MP;
void init() {
    for (int i = 1; i <= INF; i++) F[i] = 1;
 
    for( auto p: s){
            for (int j = p; j <= INF; j += p) {
                F[j] *= p; 
                // MP[F[j]].pb(j);
            }
    }
    for (int i = 1; i <= INF; i++) {
        MP[F[i]].pb(i);
    }
}
 
void solve() 
{
    ll a, b; cin >> a >> b;
 
    ll res = 0;
 
    for(auto &k : MP) {
        auto &vec = k.second;
        auto l = lower_bound(vec.begin(), vec.end(), a);
        auto r = upper_bound(vec.begin(), vec.end(), b);
 
       ll n = r-l;
       //if (n !=0 ) cout << k.first << " " << n << cc;
       res += n*(n-1)/2;
    }
    cout << res << cc;
}
 
int main() {
    IOS;
    file("PRIME");
 
    init();
    int T; cin >> T;
    while(T--) {
        solve();
    }
 
 cerr << "Time : " << TIME << " ";
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGRiIGRvdWJsZQoKI2RlZmluZSBwaWkgcGFpcjxpbnQsIGludD4KCiNkZWZpbmUgdmkgdmVjdG9yPGludD4KI2RlZmluZSBJT1MgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7IGNpbi50aWUoTlVMTCkKCi8vcGFpcnMKI2RlZmluZSBmcyBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAoKLy92ZWN0b3JzCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgcGYgcHVzaF9mcm9udAoKLy9sb29wcwojZGVmaW5lIEZPUihpLCBhLCBiKSBmb3IoaW50IGk9KGludClhO2k8PShpbnQpYjsrK2kpCiNkZWZpbmUgUk9GKGksIGEsIGIpIGZvcihpbnQgaT0oaW50KWE7aT49KGludCliO2ktLSkKI2RlZmluZSByZXAoYSwgeCkgZm9yKGF1dG8mIGEgOiB4KQojZGVmaW5lIGNjICdcbicKCi8vZmlsZQojZGVmaW5lIGZpbGUobmFtZSkgaWYgKGZvcGVuKG5hbWUiLmlucCIsICJyIikpIGZyZW9wZW4obmFtZSIuaW5wIiwgInIiLCBzdGRpbiksIGZyZW9wZW4obmFtZSIub3V0IiwgInciLCBzdGRvdXQpCiNkZWZpbmUgVElNRSAoMS4wICogY2xvY2soKSAvIENMT0NLU19QRVJfU0VDKQoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBtYXhuID0gNSoxZTMrNzsKY29uc3QgbGwgSU5GID0gMWU2OwoKLy9+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+flwKLy9+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn5+fn4KbGwgRltJTkYrMV07CmxsIHNbN10gPSB7MiwzLDUsNywxMSwxMywxN307Cm1hcCA8bGwsIHZlY3RvcjxsbD4+TVA7CnZvaWQgaW5pdCgpIHsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IElORjsgaSsrKSBGW2ldID0gMTsKCiAgICBmb3IoIGF1dG8gcDogcyl7CiAgICAgICAgICAgIGZvciAoaW50IGogPSBwOyBqIDw9IElORjsgaiArPSBwKSB7CiAgICAgICAgICAgICAgICBGW2pdICo9IHA7IAogICAgICAgICAgICAgICAgLy8gTVBbRltqXV0ucGIoaik7CiAgICAgICAgICAgIH0KICAgIH0KICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IElORjsgaSsrKSB7CiAgICAgICAgTVBbRltpXV0ucGIoaSk7CiAgICB9Cn0KCnZvaWQgc29sdmUoKSAKewogICAgbGwgYSwgYjsgY2luID4+IGEgPj4gYjsKICAgCiAgICBsbCByZXMgPSAwOwoKICAgIGZvcihhdXRvICZrIDogTVApIHsKICAgICAgICBhdXRvICZ2ZWMgPSBrLnNlY29uZDsKICAgICAgICBhdXRvIGwgPSBsb3dlcl9ib3VuZCh2ZWMuYmVnaW4oKSwgdmVjLmVuZCgpLCBhKTsKICAgICAgICBhdXRvIHIgPSB1cHBlcl9ib3VuZCh2ZWMuYmVnaW4oKSwgdmVjLmVuZCgpLCBiKTsKCiAgICAgICBsbCBuID0gci1sOwogICAgICAgLy9pZiAobiAhPTAgKSBjb3V0IDw8IGsuZmlyc3QgPDwgIiAiIDw8IG4gPDwgY2M7CiAgICAgICByZXMgKz0gbioobi0xKS8yOwogICAgfQogICAgY291dCA8PCByZXMgPDwgY2M7Cn0KCmludCBtYWluKCkgewogICAgSU9TOwogICAgZmlsZSgiUFJJTUUiKTsKCiAgICBpbml0KCk7CiAgICBpbnQgVDsgY2luID4+IFQ7CiAgICB3aGlsZShULS0pIHsKICAgICAgICBzb2x2ZSgpOwogICAgfQogICAKIGNlcnIgPDwgIlRpbWUgOiAiIDw8IFRJTUUgPDwgIiAiOwp9

MwoxIDEwCjEgNQozIDU=

3
1 10
1 5
3 5