// File generated on 24/11/13 21:58 by Anand

#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false); cin.tie(0)
#define rep(i, m, n)  for (long long i = m; i < n; i++)
#define DEBUG(x) cout << "debug: " << x << "\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define pb push_back
#define sz size

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vec;
typedef vector<vec> vecc;
typedef vector<pll> vecp;

ll f(ll n) {
    ll c = 0;
    if (n%2==0) c++;
    while(n%2==0) n/=2;

    for(ll i = 3; i <= sqrtl(n); i+=2) {
        if (n == 1) break;
        if (n%i==0) c++;
        while(n%i==0) n/=i;
    }

    if (n > 2) c++;

    return c;
}

ll N = 1e7 + 1;

void SOLVE() {
    vec a(N);
    vec b(N);
    rep(i,2,N) {
        if (f(i)&1) {b[i] = b[i-1] + 1; a[i] = a[i-1];}
        else {a[i] = a[i - 1] + 1; b[i] = b[i-1];}
    }

    ll n;
    cin >> n;
    while(n--) {
        ll l, r;
        cin >> l >> r;
        cout << a[r] - a[l - 1] - b[r] + b[l - 1] << "\n";
    }
}

signed main() {
    fastio;


		SOLVE();

    return 0;
}