#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int *v = (long long int *)calloc(5000001, sizeof(long long int));
  for (long long int i = 2; i < 5000001; i++) {
    if (v[i] == 0) {
      for (long long int j = i; j < 5000001; j = j + i) {
        v[j] = v[j / i] + 1;
      }
    }
  }
  for (long long int i = 2; i < 5000001; i++) v[i] = v[i - 1] + v[i];
  long long int t;
  cin >> t;
  for (long long int t1 = 0; t1 < t; t1++) {
    long long int a, b;
    scanf("%ld %ld", &a, &b);
    printf("%ld\n", v[a] - v[b]);
  }
  return 0;
}
