#include <bits/stdc++.h>
using namespace std;
template <class T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <class T>
T my_pow(T n, T p) {
  if (p == 0) return 1;
  T x = my_pow(n, p / 2);
  x = (x * x);
  if (p & 1) x = (x * n);
  return x;
}
template <class T>
T big_mod(T n, T p, T m) {
  if (p == 0) return (T)1;
  T x = big_mod(n, p / 2, m);
  x = (x * x) % m;
  if (p & 1) x = (x * n) % m;
  return x;
}
template <class T>
T extract(string s, T ret) {
  stringstream ss(s);
  ss >> ret;
  return ret;
}
string itos(long long n) {
  string s;
  while (n) {
    s += (n % 10 + 48);
    n /= 10;
  }
  reverse(s.begin(), s.end());
  return s;
}
long long stoi(string s) {
  long long n = 0;
  for (__typeof(s.size()) i = 0; i < (s.size()); i++) n = n * 10 + (s[i] - 48);
  return n;
}
double DEG(double x) { return (180.0 * x) / (acos(-1.0)); }
double RAD(double x) { return (x * (double)acos(-1.0)) / (180.0); }
template <typename T>
T DIS(T x1, T y1, T x2, T y2) {
  return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
template <typename T>
T ANGLE(T x1, T y1, T x2, T y2) {
  return atan(double(y1 - y2) / double(x1 - x2));
}
template <typename T>
long long isLeft(T a, T b, T c) {
  return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
const int N = 5e6 + 5, MOD = 1e9 + 7;
long long ar[N], br[N];
long long a = 0, b = 0, c = 0, r = 0, rr = 0, res = 0, n, m, t = 0, ks = 0;
string s;
void prime() {
  for (int i = 2; i <= 5000000; i += 2) ar[i] = 2;
  for (long long i = 3; i <= 5000000; i += 2) {
    if (ar[i] == 0) {
      ar[i] = i;
      for (long long j = i * i * 1LL; j <= 5000000; j += 2 * i) ar[j] = i;
    }
  }
}
long long factor(long long n) {
  int c = 0;
  while (n != 1) {
    long long aa = ar[n];
    while (n % aa == 0) {
      c++;
      n /= aa;
    }
  }
  return c;
}
int main() {
  prime();
  for (long long i = 2; i <= 5000000; i++) {
    br[i] = br[i - 1] + factor(i);
  }
  scanf("%lld", &t);
  while (t--) {
    scanf("%lld", &n);
    scanf("%lld", &m);
    printf("%lld\n", br[n] - br[m]);
  }
  return 0;
}
