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

bool _isPrime(N)(N n) if (isNumeric!N) {
  if (n <= 1) {
    return false;
  } else if (n == 2) {
    return true;
  } else if (n % 2 == 0) {
    return false;
  }

  for (N i = 3; i * i <= n; i += 2) {
    if (n % i == 0) {
      return false;
    }
  }

  return true;
}

alias isPrime = memoize!(_isPrime!(ulong));

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

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

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

    while (x <= r) {
      if (isLike2017(x)) { t++; }
      x++;
    }

    writeln(t);
  }
}
