function myout(text){console.log(text);}//standard output
function Main(input) {
	//input = parseInt(input);
	//input = input.trim().split(" ");
	input = input.trim().split("\n");
	//input = input.trim().split(" ").map((a)=>Number(a));
	//input = input.trim().split("\n").map((a)=>Number(a));
  var list = [0];//2017数の累積
  var count = 0;
  var output = [];
  for(var i = 1; i <= 100000; i++){
    if(i % 2 == 1 && isPrime(i) && isPrime((i + 1) / 2)){
       count++;
    }
    list.push(count);
  }
  
  var Q = parseInt(input[0]);
  for(var i = 1; i <= Q; i++){
    var L = parseInt(input[i].split(" ")[0]);
    var R = parseInt(input[i].split(" ")[1]);
    var add = list[R] - list[L];
    if(isPrime(L) && isPrime((L + 1) / 2)){
       add++;
       }
    output.push(add);
  }
  //myout(list[13]);
  //myout(list[12]);
  //myout(list[91]);
  myout(output.join("\n"));
}

//素数判定(高速)
function isPrime(val){
	if(val == 1 || (val != 2 && val % 2 == 0)){
		return false;
	}else if(val == 2){
		return true;
	}
	var root = Math.floor(Math.sqrt(val));
	for(var i = 3; i <= root; i += 2){
		if(val % i == 0){
			return false;
		}
	}
	return true;
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());
