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(int n) {
  __isPrime[0] = false;
  __isPrime[1] = false;
  __isPrime[2] = true;
  if (n < 3) return;
  foreach (i; 3..n+1) {
    __isPrime[i] = true;
    for (int j = 2; j * j <= i; j += 2) {
      if (i % j == 0) {
        __isPrime[i] = false;
        break;
      }
    }
  }
}

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;

  init__isPrime(10^^5);

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

    while (x <= r) {
      if (x in like2017) {
        t++;
      } else if (isLike2017(x)) {
        t++;
        like2017[x] = true;
      }
      x++;
    }

    writeln(t);
  }
}
