/* imports all std modules {{{*/
import
  std.algorithm,
  std.array,
  std.ascii,
  std.base64,
  std.bigint,
  std.bitmanip,
  std.compiler,
  std.complex,
  std.concurrency,
  std.container,
  std.conv,
  std.csv,
  std.datetime,
  std.demangle,
  std.encoding,
  std.exception,
  std.file,
  std.format,
  std.functional,
  std.getopt,
  std.json,
  std.math,
  std.mathspecial,
  std.meta,
  std.mmfile,
  std.net.curl,
  std.net.isemail,
  std.numeric,
  std.parallelism,
  std.path,
  std.process,
  std.random,
  std.range,
  std.regex,
  std.signals,
  std.socket,
  std.stdint,
  std.stdio,
  std.string,
  std.system,
  std.traits,
  std.typecons,
  std.uni,
  std.uri,
  std.utf,
  std.uuid,
  std.variant,
  std.zip,
  std.zlib;
/*}}}*/

/+---test
1
3 7
---+/
/+---test
4
13 13
7 11
7 11
2017 2017
---+/

void main(string[] args) {
  enum N = 100000;
  const Q = readln.chomp.to!long;

  auto thieve = new bool[](N+1);
  thieve[] = true;
  thieve[0..2] = false;
  foreach (i; 2..N+1) {
    for (long j = i*2; j < thieve.length; j+=i) {
      thieve[j] = false;
    }
  }

  auto thieve2 = new bool[](N+1);
  foreach (i; 1..N/2+1) {
    thieve2[2*i-1] = thieve[i] && thieve[2*i-1];
  }

  auto pcnt = new long[](100001);
  foreach (i, ref c; pcnt) {
    if (i) c = pcnt[i-1] + thieve2[i];
  }

  foreach (q; 0..Q) {
    long l, r;
    readf(" %d %d ", &l, &r);
    (pcnt[r] - pcnt[l-1]).writeln;
  }
}
