#include <bits/stdc++.h>
using namespace std;
char _inp[16777217], *_pinp = _inp, _;
int QQ, a, b, cnt[5000001], sum[5000001];
int main() {
  for (int i = 2; i <= 5000000; i++)
    if (!cnt[i])
      for (int j = i; j <= 5000000; j += i) cnt[j] = cnt[j / i] + 1;
  for (int i = 2; i <= 5000000; i++) sum[i] = sum[i - 1] + cnt[i];
  do {
    while (
        (QQ = (*_pinp ? *_pinp++
                      : (_inp[fread(_pinp = _inp, 1, 16777216, stdin)] = '\0',
                         *_pinp++))) < '0')
      ;
    for (QQ -= '0';
         '0' <=
         (_ = (*_pinp ? *_pinp++
                      : (_inp[fread(_pinp = _inp, 1, 16777216, stdin)] = '\0',
                                                               *_pinp++)));
         QQ = (QQ << 3) + (QQ << 1) + _ - '0')
      ;
  } while (0);
  while (QQ--) {
    do {
      while (
          (a = (*_pinp ? *_pinp++
                       : (_inp[fread(_pinp = _inp, 1, 16777216, stdin)] = '\0',
                          *_pinp++))) < '0')
        ;
      for (a -= '0';
           '0' <=
           (_ = (*_pinp ? *_pinp++
                        : (_inp[fread(_pinp = _inp, 1, 16777216, stdin)] = '\0',
                                                                 *_pinp++)));
           a = (a << 3) + (a << 1) + _ - '0')
        ;
    } while (0);
    do {
      while (
          (b = (*_pinp ? *_pinp++
                       : (_inp[fread(_pinp = _inp, 1, 16777216, stdin)] = '\0',
                          *_pinp++))) < '0')
        ;
      for (b -= '0';
           '0' <=
           (_ = (*_pinp ? *_pinp++
                        : (_inp[fread(_pinp = _inp, 1, 16777216, stdin)] = '\0',
                                                                 *_pinp++)));
           b = (b << 3) + (b << 1) + _ - '0')
        ;
    } while (0);
    printf("%d\n", sum[a] - sum[b]);
  }
  return 0;
}
