#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){
        if (F[p] == 1) { 
            for (int j = p; j <= INF; j += p) {
                F[j] *= p; 
                MP[F[j]].pb(j);
            }
        }
    }
}
 
void solve() 
{
    ll a, b; cin >> a >> b;
    map <ll, ll > mp;
    for(ll i = a; i<= b; i++) {
        mp[F[i]]++;
    }
    ll res = 0;
    for(auto &k : mp) {
        ll n = k.second;
        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+TVA7CnZvaWQgaW5pdCgpIHsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IElORjsgaSsrKSBGW2ldID0gMTsKCiAgICBmb3IoIGF1dG8gcDogcyl7CiAgICAgICAgaWYgKEZbcF0gPT0gMSkgeyAKICAgICAgICAgICAgZm9yIChpbnQgaiA9IHA7IGogPD0gSU5GOyBqICs9IHApIHsKICAgICAgICAgICAgICAgIEZbal0gKj0gcDsgCiAgICAgICAgICAgICAgICBNUFtGW2pdXS5wYihqKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKdm9pZCBzb2x2ZSgpIAp7CiAgICBsbCBhLCBiOyBjaW4gPj4gYSA+PiBiOwogICAgbWFwIDxsbCwgbGwgPiBtcDsKICAgIGZvcihsbCBpID0gYTsgaTw9IGI7IGkrKykgewogICAgICAgIG1wW0ZbaV1dKys7CiAgICB9CiAgICBsbCByZXMgPSAwOwogICAgZm9yKGF1dG8gJmsgOiBtcCkgewogICAgICAgIGxsIG4gPSBrLnNlY29uZDsKICAgICAgICByZXMgKz0gbioobi0xKSAvIDI7CiAgICB9CiAgICBjb3V0IDw8IHJlcyA8PCBjYzsKfQoKaW50IG1haW4oKSB7CiAgICBJT1M7CiAgICBmaWxlKCJQUklNRSIpOwoKICAgIGluaXQoKTsKICAgIGludCBUOyBjaW4gPj4gVDsKICAgIHdoaWxlKFQtLSkgewogICAgICAgIHNvbHZlKCk7CiAgICB9CiBjZXJyIDw8ICJUaW1lIDogIiA8PCBUSU1FIDw8ICIgIjsKfQ==

MgoxIDUKMSAxMA==

2
1 5
1 10