#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];
void init() {
    for (int i = 1; i <= INF; i++) F[i] = 1;
 
    for (int p = 2; p <= INF; p++) {
        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+fn4KbGwgRltJTkYrMV07CnZvaWQgaW5pdCgpIHsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IElORjsgaSsrKSBGW2ldID0gMTsKCiAgICBmb3IgKGludCBwID0gMjsgcCA8PSBJTkY7IHArKykgewogICAgICAgIGlmIChGW3BdID09IDEpIHsgCiAgICAgICAgICAgIGZvciAoaW50IGogPSBwOyBqIDw9IElORjsgaiArPSBwKSB7CiAgICAgICAgICAgICAgICBGW2pdICo9IHA7IAogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIHNvbHZlKCkgCnsKICAgIGxsIGEsIGI7IGNpbiA+PiBhID4+IGI7CiAgICBtYXAgPGxsLCBsbCA+IG1wOwogICAgZm9yKGxsIGkgPSBhOyBpPD0gYjsgaSsrKSB7CiAgICAgICAgbXBbRltpXV0rKzsKICAgIH0KICAgIGxsIHJlcyA9IDA7CiAgICBmb3IoYXV0byAmayA6IG1wKSB7CiAgICAgICAgbGwgbiA9IGsuc2Vjb25kOwogICAgICAgIHJlcyArPSBuKihuLTEpIC8gMjsKICAgIH0KICAgIGNvdXQgPDwgcmVzIDw8IGNjOwp9CgppbnQgbWFpbigpIHsKICAgIElPUzsKICAgIGZpbGUoIlBSSU1FIik7CgogICAgaW5pdCgpOwogICAgaW50IFQ7IGNpbiA+PiBUOwogICAgd2hpbGUoVC0tKSB7CiAgICAgICAgc29sdmUoKTsKICAgIH0KIGNlcnIgPDwgIlRpbWUgOiAiIDw8IFRJTUUgPDwgIiAiOwp9Cg==

MgoxIDUKMSAxMA==

2
1 5
1 10