// 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 = 0;

void SOLVE() {
    ll n; cin >> n;
    vecp u(n);
    rep(i,0,n) {ll x, y; cin >> x >> y; u[i] = {x,y}; N = max(N, y);}
    N++;
    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];}
    }

    rep(i,0,n) {
        ll l = u[i].first;
        ll r = u[i].second;
        cout << a[r] - a[l - 1] - b[r] + b[l - 1] << "\n";
    }
}

signed main() {
    fastio;


		SOLVE();

    return 0;
}