#include <bits/stdc++.h>
using namespace std;
int arr[5000001] = {0}, primefac[5000001], primediv[5000001];
int main() {
  int t, i, a, b, sum, j;
  primefac[1] = 0;
  for (i = 2; i <= 5000000; ++i) {
    if (arr[i] == 0) {
      primefac[i] = 1;
      primediv[i] = i;
      arr[i] = 1;
      for (j = 2; j * i <= 5000000; ++j) {
        arr[j * i] = 1;
        primediv[i * j] = i;
      }
    }
  }
  for (i = 2; i <= 5000000; ++i) primefac[i] = primefac[i / primediv[i]] + 1;
  for (i = 3; i <= 5000000; ++i) primefac[i] += primefac[i - 1];
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &a, &b);
    printf("%d\n", primefac[a] - primefac[b]);
  }
  return 0;
}
