#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long HASH = 1e16 + 7;
long long tavan(long long a, long long b) {
  return b ? (tavan(a * a, b >> 1) * (b & 1 ? a : 1)) : 1;
}
long long gcd(long long a, long long b) {
  return (a < b) ? gcd(b, a) : ((a % b == 0) ? b : gcd(b, a % b));
}
bool isprime(long long x) {
  for (long long i = 2; i <= sqrt(x); i++)
    if (!(x % i)) return false;
  return true;
}
ifstream fin("input.txt");
ofstream fout("output.txt");
int t, a, b, dp[(5000 * 1000 + 5)];
int main() {
  scanf("%d", &t);
  for (int i = 2; i < (5000 * 1000 + 5); i++) {
    if (!dp[i])
      for (int j = i; j < (5000 * 1000 + 5); j += i) {
        int ex = j;
        while (ex % i == 0) {
          ex /= i;
          dp[j]++;
        }
      }
  }
  for (int i = 2; i < (5000 * 1000 + 5); i++) dp[i] += dp[i - 1];
  while (t) {
    scanf("%d%d", &a, &b);
    printf("%d\n", dp[a] - dp[b]);
    t--;
  }
  return 0;
}
