#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int MAX = 5000001;
unsigned int arr[MAX], P[MAX];
void sieve() {
  unsigned int i, j, t, k;
  arr[0] = arr[1] = 0;
  for (i = 2; i < MAX; i++) arr[i] = i;
  for (i = 4; i < MAX; i += 2) arr[i] = 2;
  for (i = 3; i * i <= MAX; i += 2)
    if (arr[i] == i)
      for (j = i * i; j < MAX; j += 2 * i)
        if (arr[j] == j) arr[j] = i;
  for (i = 2; i < 5000001; i++) P[i] = P[i / arr[i]] + 1;
  for (i = 2; i < 5000001; i++) P[i] += P[i - 1];
}
int main(void) {
  sieve();
  unsigned int tc, i, a, b;
  scanf("%u", &tc);
  for (i = 1; i <= tc; i++) {
    scanf("%u %u", &a, &b);
    printf("%u\n", P[a] - P[b]);
  }
  return 0;
}
