#include <bits/stdc++.h>
using namespace std;
int sieve[5000001];
long long int nf[5000001];
long long int pre[5000001];
int highestPow(int a, int x) {
  if (x > a) return 0;
  int k = x;
  int sum = 0;
  while ((a / k) > 0) {
    sum += (a / k);
    k *= x;
  }
  return sum;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  for (int i = 2; i <= 5000000; i++) sieve[i] = i;
  for (int i = 2; i * i <= 5000000; i++) {
    if (sieve[i] == i) {
      for (int j = 2 * i; j <= 5000000; j += i) {
        if (sieve[j] == j) sieve[j] = i;
      }
    }
  }
  nf[0] = nf[1] = 0;
  for (int i = 2; i <= 5000000; i++) {
    nf[i] = nf[i / sieve[i]] + 1;
  }
  for (int i = 1; i <= 5000000; i++) {
    pre[i] = nf[i] + pre[i - 1];
  }
  int t;
  cin >> t;
  while (t--) {
    int a, b;
    cin >> a >> b;
    int m = max(a, b);
    cout << pre[a] - pre[b] << '\n';
  }
}
