// import chie template :) {{{
import std.stdio,
       std.algorithm,
       std.array,
       std.string,
       std.math,
       std.conv,
       std.range,
       std.container,
       std.bigint;
// }}}

void main() {
  bool[101010] e;
  e[2 .. 101010] = true;
  e[0 .. 2] = false;
  foreach (i; 2 .. 101010) {
    if (e[i]) {
      for (int j = i * i; j < e.length; j += i) e[j] = false;
    }
  }
  long[101010] sum;

  for (int i = 1; i < e.length; i += 2) {
    if (e[i] && e[(i + 1) / 2]) sum[i] = 1;
  }
  foreach (i; 1 .. 101010) {
    sum[i] += sum[i - 1];
  }

  int q = readln.chomp.to!int;
  foreach (i; 0 .. q) {
    int[] ra = readln.chomp.split.to!(int[]);
    writeln(sum[ra[1]] - sum[ra[0] - 1]);
  }
}
