#include <bits/stdc++.h>
using namespace std;
const int MAXn = 5 * 1000 * 1000;
int s[MAXn + 5], dp[MAXn + 5];
int main() {
  int t;
  for (int i = 2; i <= MAXn; i++) s[i] = INT_MAX;
  for (int i = 2; i <= MAXn; i++) {
    if (s[i] == INT_MAX)
      for (int j = 1; i * j <= MAXn; j++) s[i * j] = min(s[i * j], i);
  }
  dp[1] = 0;
  for (int i = 2; i <= MAXn; i++)
    if (s[i] == i)
      dp[i] = 1;
    else
      dp[i] = dp[i / s[i]] + 1;
  for (int i = 2; i <= MAXn; i++) dp[i] += dp[i - 1];
  scanf("%d", &t);
  for (int i = 0; i < t; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", dp[a] - dp[b]);
  }
  return 0;
}
