'use strict';
console.log(function(args){
  const tmp = args.trim().split('\n').map( r=>r.split(' ').map(v=>v|0) );
  const Q = tmp.shift()[0];
  const MAX = 50000;
  const a = Array(MAX).fill(1);
  const s = Array(MAX+1).fill(0);
  a[0] = 0; a[1] = 1; s[0] = s[1] = 0; s[2] = 1;
   for ( let i = 1; i < MAX; i++ ) {
    if ( !a[i] ) continue;
    const n = 2*i+1;
    if ( ~i&1 && a[i/2] ) s[i+1] = 1;
    for ( let j = i+n; j < MAX; j=j+n ) a[j] = 0;
  }
  for ( let i = 2; i < MAX; i++ ) {
    s[i] += s[i-1];
  }
  let x = [];
  for ( let i = 0; i < Q; i++ ) {
    const l = ( tmp[i][0] - 1 ) / 2;
    const r = ( tmp[i][1] - 1 ) / 2 + 1;
    x.push( s[r] - s[l] );
  }
  return x.join('\n');
}(require('fs').readFileSync('/dev/stdin', 'utf8')));
