#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};
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; 
            }
        }
    }
}
 
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+fn4KbGwgRltJTkYrMV07CmxsIHNbN10gPSB7MiwzLDUsNywxMSwxMywxN307CnZvaWQgaW5pdCgpIHsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IElORjsgaSsrKSBGW2ldID0gMTsKCiAgICBmb3IoIGF1dG8gcDogcyl7CiAgICAgICAgaWYgKEZbcF0gPT0gMSkgeyAKICAgICAgICAgICAgZm9yIChpbnQgaiA9IHA7IGogPD0gSU5GOyBqICs9IHApIHsKICAgICAgICAgICAgICAgIEZbal0gKj0gcDsgCiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCnZvaWQgc29sdmUoKSAKewogICAgbGwgYSwgYjsgY2luID4+IGEgPj4gYjsKICAgIG1hcCA8bGwsIGxsID4gbXA7CiAgICBmb3IobGwgaSA9IGE7IGk8PSBiOyBpKyspIHsKICAgICAgICBtcFtGW2ldXSsrOwogICAgfQogICAgbGwgcmVzID0gMDsKICAgIGZvcihhdXRvICZrIDogbXApIHsKICAgICAgICBsbCBuID0gay5zZWNvbmQ7CiAgICAgICAgcmVzICs9IG4qKG4tMSkgLyAyOwogICAgfQogICAgY291dCA8PCByZXMgPDwgY2M7Cn0KCmludCBtYWluKCkgewogICAgSU9TOwogICAgZmlsZSgiUFJJTUUiKTsKCiAgICBpbml0KCk7CiAgICBpbnQgVDsgY2luID4+IFQ7CiAgICB3aGlsZShULS0pIHsKICAgICAgICBzb2x2ZSgpOwogICAgfQogY2VyciA8PCAiVGltZSA6ICIgPDwgVElNRSA8PCAiICI7Cn0=

MgoxIDUKMSAxMA==

2
1 5
1 10