#include <bits/stdc++.h>
using namespace std;
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
inline void read(int &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = 10 * x + c - '0';
    c = getchar();
  }
  x *= f;
}
void printDouble(double x, int n) {
  cout << fixed << setprecision(n);
  cout << x << endl;
}
const int NMAX = 5000000;
int main() {
  vector<bool> isPrime(NMAX + 1, true);
  vector<int> prime, divisor(NMAX + 1, 0), s(NMAX + 1, 0);
  for (int i = 2; i <= NMAX; i++)
    if (isPrime[i]) {
      prime.push_back(i);
      for (int j = 2; j <= NMAX / i; j++) isPrime[i * j] = false;
    }
  for (int i = 2; i <= NMAX; i++)
    if (isPrime[i]) {
      divisor[i] = 1;
      for (auto j : prime)
        if (j * i > NMAX)
          break;
        else
          divisor[i * j] = 2;
    } else
      for (auto j : prime)
        if (i % j == 0 && divisor[i / j] != 0) {
          divisor[i] = divisor[i / j] + 1;
          break;
        }
  for (int i = 1; i <= NMAX; i++) s[i] = s[i - 1] + divisor[i];
  int t, x, y;
  read(t);
  for (int i = 1; i <= t; i++) {
    read(x);
    read(y);
    cout << s[x] - s[y] << endl;
  }
}
