#include <assert.h>
#include <limits.h>
#include <math.h>

#include <algorithm>
#include <bit>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
#define ll long long
#define ld long double
#define vll vector<ll>
#define vvll vector<vll>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vs vector<string>
#define pi pair<int, int>
#define vpi vector<pi>
#define vvpi vector<vpi>
#define pll pair<ll, ll>
#define ppll pair<pll, pll>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define PB push_back
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
double EPS = 1e-18;
// const vpi MOVES_ADJACENT{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
// const vpi MOVES_ALL{{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0,
// -1}, {1, -1}};

template <typename T>
void db(T const& coll) {
    typename T::const_iterator pos;
    typename T::const_iterator end(coll.end());

    for (pos = coll.begin(); pos != end; ++pos) {
        cout << *pos << ' ';
    }
    cout << "\n";
}

void ans(ll x) { cout << (x == 0 ? "YES" : "NO") << "\n"; }

ll MAXN = 1e7;
// ll MAXN = 1e5;
// ll MAXN = 50;
vector<bool> is_prime(MAXN + 5, true);
vll primes;
vll dcount(MAXN + 5, 0);
void init() {
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i * i <= MAXN; i++) {
        if (is_prime[i]) {
            for (ll j = i * i; j <= MAXN; j += i) is_prime[j] = false;
        }
    }
    dcount[1] = 1;
    deque<ll> q;
    for (ll i = 1; i <= MAXN; ++i) {
        if (is_prime[i]) primes.PB(i);
    }
    vll index(MAXN + 5, -1);
    for (ll i = 0; i < primes.size(); ++i) {
        ll p = primes[i];
        dcount[p] = 1;
        index[p] = i; // index of the prime, to reference next
        q.PB(p);
    }
    // db(q);
    ll count = q.size();
    while (!q.empty()) {
        ll x = q.front(); q.pop_front();
        // cout << "AT " << x << "\n";
        for (ll next_index = index[x];
             next_index < primes.size() && x * primes[next_index] <= MAXN;
             ++next_index) {
            // cout << " MUL WITH " << primes[next_index] << "\n";
            ll v = x * primes[next_index];
            if (index[x] == next_index) {
                dcount[v] = dcount[x];
            } else {
                dcount[v] = dcount[x] + 1;
            }
            index[v] = next_index;
            q.PB(v);
        }
    }
    // cout << count << "\n";
    // for (ll i = 0; i <= MAXN; ++i) cout << i << " ";
    // cout << "\n";
    // db(dcount);
    // db(primes);
    // db(dcount);
    // db(index);
}
void solve() {
    vll pref(MAXN+5, 0);
    for (ll i = 1; i <= MAXN; ++i) {
        pref[i] += pref[i-1] + (dcount[i]%2==0);
    }
    ll n;
    cin >> n;
    ll l, r;
    for (ll i = 0; i < n; ++i) {
        cin >> l >> r;
        ll total = r - l + 1;
        ll evens = pref[r] - pref[l-1];
        cout << evens - (total-evens) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();
    // ll t;
    // cin >> t;
    // while (t--) {
    //     solve();
    // }

    solve();
}