# ABC084D - 2017-like Number

from bisect import bisect_left as bsl, bisect_right as bsr





def get_primes(n: int) -> list:

    # return a list of primes <= n

    sieve = [1] * n

    for i in range(3, int(n ** 0.5) + 1, 2):

        if sieve[i]:

            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)

    return [2] + [i for i in range(3, n, 2) if sieve[i]]





def main():

    Q, *LR = map(int, open(0).read().split())

    P = get_primes(10 ** 5 + 1)

    S = set(P)

    sel = [p for p in P if (p + 1) // 2 in S]  # 2017-like primes (selected P)

    # the number of 2017-like primes b/w l, r -> bisect[r] - bisect[l]

    ans = [bsr(sel, r) - bsl(sel, l) for l, r in zip(*[iter(LR)] * 2)]

    print(*ans, sep="\n")





if __name__ == "__main__":

    main()

# D - 2017-like Number

from itertools import accumulate

from math import sqrt





def get_primes(n: int) -> set:

    """Return a list of prime numbers < n in O(N)."""

    if n < 2:

        return set()



    sieve = [1] * n

    for i in range(3, int(sqrt(n)) + 1, 2):

        if sieve[i]:

            sieve[i * i:: 2 * i] = [0] * ((n - i ** 2 - 1) // (2 * i) + 1)

    return {2} | {i for i in range(3, n, 2) if sieve[i]}





def main():

    Q, *LR = list(map(int, open(0).read().split()))

    primes = get_primes(10 ** 5 + 1)

    is_2017_like = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(10 ** 5 + 1)]

    cumsum = tuple(accumulate(is_2017_like))

    ans = []

    for l, r in zip(*[iter(LR)] * 2):

        ans.append(cumsum[r] - cumsum[l - 1])

    print(("\n".join(map(str, ans))))





if __name__ == "__main__":

    main()

# ABC084D - 2017-like Number
from bisect import bisect_left as bsl, bisect_right as bsr


def get_primes(n: int) -> list:
    # return a list of primes <= n
    sieve = [1] * n
    for i in range(3, int(n**0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q, *LR = map(int, open(0).read().split())
    P = get_primes(10**5 + 1)
    S = set(P)
    sel = [p for p in P if (p + 1) // 2 in S]  # 2017-like primes (selected P)
    # the number of 2017-like primes b/w l, r -> bisect[r] - bisect[l]
    ans = [bsr(sel, r) - bsl(sel, l) for l, r in zip(*[iter(LR)] * 2)]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

# D - 2017-like Number
from itertools import accumulate
from math import sqrt


def get_primes(n: int) -> set:
    """Return a list of prime numbers < n in O(N)."""
    if n < 2:
        return set()
    sieve = [1] * n
    for i in range(3, int(sqrt(n)) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i**2 - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if sieve[i]}


def main():
    Q, *LR = list(map(int, open(0).read().split()))
    primes = get_primes(10**5 + 1)
    is_2017_like = [
        1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(10**5 + 1)
    ]
    cumsum = tuple(accumulate(is_2017_like))
    ans = []
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(cumsum[r] - cumsum[l - 1])
    print(("\n".join(map(str, ans))))


if __name__ == "__main__":
    main()

-# ABC084D - 2017-like Number -from bisect import bisect_left as bsl, bisect_right as bsr +# D - 2017-like Number +from itertools import accumulate +from math import sqrt -def get_primes(n: int) -> list: -    # return a list of primes <= n +def get_primes(n: int) -> set: +    """Return a list of prime numbers < n in O(N).""" +    if n < 2: +        return set() -    for i in range(3, int(n**0.5) + 1, 2): +    for i in range(3, int(sqrt(n)) + 1, 2): -            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1) -    return [2] + [i for i in range(3, n, 2) if sieve[i]] +            sieve[i * i :: 2 * i] = [0] * ((n - i**2 - 1) // (2 * i) + 1) +    return {2} | {i for i in range(3, n, 2) if sieve[i]} -    Q, *LR = map(int, open(0).read().split()) -    P = get_primes(10**5 + 1) -    S = set(P) -    sel = [p for p in P if (p + 1) // 2 in S]  # 2017-like primes (selected P) -    # the number of 2017-like primes b/w l, r -> bisect[r] - bisect[l] -    ans = [bsr(sel, r) - bsl(sel, l) for l, r in zip(*[iter(LR)] * 2)] -    print(*ans, sep="\n") +    Q, *LR = list(map(int, open(0).read().split())) +    primes = get_primes(10**5 + 1) +    is_2017_like = [ +        1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(10**5 + 1) +    ] +    cumsum = tuple(accumulate(is_2017_like)) +    ans = [] +    for l, r in zip(*[iter(LR)] * 2): +        ans.append(cumsum[r] - cumsum[l - 1]) +    print(("\n".join(map(str, ans))))