import std.functional,
       std.algorithm,
       std.bigint,
       std.string,
       std.traits,
       std.array,
       std.range,
       std.stdio,
       std.conv;

bool[int] isPrime;

void init_isPrime() {
  foreach (i; 1..10^^5+1) {
    isPrime[i] = true;
  }

  foreach (i; 2..100001) {
    if (isPrime[i]) {
      for (int j = i + i; j <= 100000; j += i){
        isPrime[j] = false;
      }
    }
  }
}

bool isLike2017(int n) {
  return isPrime[n] && isPrime[(n+1)/2];
}

void main() {
  int Q = readln.chomp.to!int;
  bool[int] like2017;
  int[][] lrs = Q.iota.map!(_ => readln.chomp.split.to!(int[])).array;
  int[100001] dp;
  
  init_isPrime();

  for (int i = 3; i <= 100000; i += 2) {
    if (isLike2017(i)) {
      dp[i]++;
    }
  }

  for (int i = 3; i <= 100000; i++) {
    dp[i] += dp[i-1];
  }

  foreach (lr; lrs) {
    int l = lr[0],
        r = lr[1];

    writeln(dp[r] - dp[l-1]);
  }
}
