function Main(input){
  var inp = input.split('\n');
  var inp1 = [];

// N, l, r を取得
  for(var i = 0; i < inp.length; i++){
    inp1.push(inp[i].split(' ').map((n) => { return parseInt(n)}));
  }

  var N = inp1[0][0];
  var l = [];
  var r = [];
  for(var i = 1; i < inp1.length; i++){
    l.push(inp1[i][0]);
    r.push(inp1[i][1]);
  }

// 
  var f = []; // 素数ならば true を格納する配列
  for(var i = 2; i <= 100000; i++){  
    if(!f[i]){
      for(var j = i + i; j <= 100000; j += i){
        f[j] = true;
      }
    }
  }

  var c = [];
  for(var i = 0; i <= 100001; i++) c[i] = 0; // 配列cを0で埋める

  for(var i = 3; i <= 100000; i += 2){ // 奇数のうち、'2017に似た数を配列cにリスト
    if(!f[i] && !f[(i + 1) / 2]){
      c[i]++;
    }
  }
  for(var i = 3; i <= 100000; i++){  // 配列cの、その添字までの和を上書き
    c[i] += c[i - 1];
  }

//  while(N--){
  for(var i = 0; i < N; i++){
    console.log(c[r[i]] - c[l[i] - 1]);
  }

}
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));