#include <bits/stdc++.h>
using namespace std;
int sp[10000010];
bitset<10000010> bs;
vector<int> primes;
long long num[5000008];
void sieve(long long upperbound) {
  long long sieve_size = upperbound + 1;
  bs.set();
  bs[0] = bs[1] = 0;
  for (long long i = 2; i <= sieve_size; i += 1)
    if (bs[i]) {
      sp[i] = i;
      for (long long j = i * i; j <= sieve_size; j += i) {
        if (bs[j]) sp[j] = i;
        bs[j] = 0;
      }
      primes.push_back((int)i);
    }
}
int factors_num(int i) {
  int ret = 0;
  while (i != 1) {
    ret++;
    i /= sp[i];
  }
  return ret;
}
int main() {
  sieve(10000000);
  int tc;
  scanf("%d", &tc);
  num[0] = 0;
  for (int i = 1; i < 5000001; i++) {
    num[i] = factors_num(i);
    num[i] += num[i - 1];
  }
  while (tc--) {
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d\n", (int)(num[n] - num[m]));
  }
}
