#include <bits/stdc++.h>
using namespace std;
template <class A, class B>
ostream &operator<<(ostream &out, const pair<A, B> &a) {
  return out << "(" << a.first << "," << a.second << ")";
}
template <class A>
ostream &operator<<(ostream &out, const vector<A> &a) {
  for (const A &it : a) out << it << " ";
  return out;
}
template <class A, class B>
istream &operator>>(istream &in, pair<A, B> &a) {
  return in >> a.first >> a.second;
}
template <class A>
istream &operator>>(istream &in, vector<A> &a) {
  for (A &i : a) in >> i;
  return in;
}
ifstream cinn("in.txt");
ofstream coutt("out.txt");
int poww(const int &a, int b, const int &m = (1000000007)) {
  if (b == 0) return 1;
  int x = poww(a, b / 2, m);
  x = x * x % m;
  if (b & 1) x = x * a % m;
  return x;
}
int ceil(const int &a, const int &b) { return (a - 1) / b + 1; }
int primes[5000005];
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 2; i < 5000005; i++) {
    if (primes[i]) continue;
    for (int j = i; j < 5000005; j += i) {
      int in = j;
      while (in % i == 0) {
        in /= i;
        primes[j]++;
      }
    }
  }
  for (int i = 1; i < 5000005; i++) primes[i] += primes[i - 1];
  int t;
  cin >> t;
  while (t--) {
    int a, b;
    cin >> a >> b;
    cout << primes[a] - primes[b] << "\n";
  }
}
