import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons;


void main() {
    enum N = 100_000;
    auto primeList = new bool[N+1];
    auto list = iota(2, N+1).array;
    while (list.front * list.front <= N) {
        primeList[list.front] = true;
        list = list[1..$].filter!(x => x % list.front).array;
    }
    foreach (x; list) {
        primeList[x] = true;
    }
    auto Q = readln.chomp.to!int;
    int[][] ranges;
    foreach (i; 0..Q) {
        auto range = readln.split.to!(int[]);
        ranges ~= range;
    }
    auto list2 = primeList.enumerate.map!(a => a.value && primeList[(a.index+1)/2] ? 1 : 0).array;
    foreach (i; 0..list2.length-1) {
        list2[i+1] += list2[i];
    }
    foreach (range; ranges) {
        if (range[0] == 0) {
            writeln(list2[range[1]]);
        } else {
            writeln(list2[range[1]] - list2[range[0]-1]);
        }
    }
}
