#include <bits/stdc++.h>
using namespace std;
int arr[5000002];
int f(int a, int b) {
  int c = 0;
  while (a % b == 0) {
    a /= b;
    c++;
  }
  return c;
}
void ans() {
  int i, j;
  for (i = 2; i < 5000002; i++) {
    if (arr[i] == 0) {
      for (j = i; j < 5000002; j += i) {
        arr[j] += f(j, i);
      }
    }
  }
}
int main() {
  ans();
  int i, j;
  for (i = 2; i < 5000002; i++) arr[i] += arr[i - 1];
  int t, a, b;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &a, &b);
    printf("%d\n", arr[a] - arr[b]);
  }
  return 0;
}
