#include <bits/stdc++.h>
using namespace std;
const int MAX = 5000000;
int p[MAX / 2 + 1];
int q[MAX + 1];
int r = 1;
void calc() {
  for (int s = 0; s <= MAX / 2; s++) {
    if (p[s]) continue;
    int t = (s + 1) * 2 + 1;
    for (int u = s; u <= MAX / 2; u += t) p[u] = t;
  }
}
int factors(int a) {
  if (a > r) {
    for (int i = r + 1; i <= a; i++) {
      int n = i, m = 0;
      while (n > 1) {
        m++;
        n /= n & 1 ? p[n / 2 - 1] : 2;
      }
      q[i] = q[i - 1] + m;
    }
    r = a;
  }
  return q[a];
}
int main(int argc, char **argv) {
  calc();
  int t;
  scanf("%d", &t);
  for (int i = 0; i < t; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", factors(a) - factors(b));
  }
  return 0;
}
