function Main(input) {
    input = input.trim().split("\n").map(function(x) { return x.split(" ")});    
    var Q = parseInt(input[0][0], 10);
    var arr_lr = [];
    var min = 1e+5;
    var max = 1;
    var line;
    for (var i = 0; i < Q; i++){
        line = input[i + 1].map(e => parseInt(e, 10));
        min = Math.min(min, line[0], line[1]);
        max = Math.max(max, line[0], line[1]);
        arr_lr.push(line);
    }
    var bin = Array.from({length: max}, () => 1);
    bin[0] = 0;
    for (var i = 2; i <= Math.sqrt(max); i++){
        for (var j = 2; j <= max / i; j++){
            bin[i * j - 1] = 0;
        }
    }
    var bin2 = Array.from({length: max}, () => 0);
    for (var i = 0; i < Math.floor((max + 1)/2); i++){
        if (bin[i] >= 1) bin2[i * 2] = 1;
    }
    var ruisekiwa = Array.from({length: max}, () => 0);
    for (var i = 1; i < ruisekiwa.length; i++){
        ruisekiwa[i] = ruisekiwa[i - 1] + bin[i] * bin2[i];
    }

    var v_ans = [];
    for (var x of arr_lr){
        if (x[0] === 1) v_ans.push(ruisekiwa[x[1] - 1]);
        else v_ans.push(ruisekiwa[x[1] - 1] - ruisekiwa[x[0] - 2]);
    }
    console.log(v_ans.join("\n"));
}

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