#include <iostream>
#include <numeric>

using namespace std;

const int MAXV = 1e7;
int dp[MAXV+1];
int minp[MAXV+1];
int main() {
  iota(minp, minp + MAXV + 1, 0);
  for(int i = 2; i * i <= MAXV; i++) {
    if(minp[i] != i) continue;
    for(int j = i*i; j <= MAXV; j += i) minp[j] = min(minp[j], i);
  }
  for(int i = 1; i <= MAXV; i++) {
    int amt = 0;
    int x = i;
    while(x > 1) {
      amt++;
      int y = minp[x];
      while(x%y==0) x /= y;
    }
    dp[i] = dp[i-1] + 2*(amt%2==0) - 1;
  }
  int q;
  cin >> q;
  while(q--) {
    int a, b;
    cin >> a >> b;
    if(false) {
      int ret = 0;
      for(int i = a; i <= b; i++) {
        int x = i;
        int amt = 0;
        while(x > 1) {
          amt++;
          int y = minp[x];
          while(x%y==0) x /= y;
        }
        if(amt%2==0) ret++;
        else ret--;
      } 
      cout << ret << "\n";
      continue;
    }
    cout << dp[b] - dp[--a] << "\n";
  }
}