import sys

from itertools import accumulate



read = sys.stdin.read

readline = sys.stdin.readline

readlines = sys.stdin.readlines

sys.setrecursionlimit(10 ** 9)

INF = 1 << 60





def prime_numbers(n):

    if n < 2:

        return []



    m = (n + 1) // 2

    p = [1] * m

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

        if p[i]:

            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)



    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}





def main():

    primes = prime_numbers(10 ** 5)

    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]

    B = [0]

    B.extend(accumulate(A))



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

    ans = [0] * Q

    for i, (l, r) in enumerate(zip(LR[::2], LR[1::2])):

        ans[i] = B[r + 1] - B[l]



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

    return





if __name__ == '__main__':

    main()

from sys import stdin, setrecursionlimit

from itertools import accumulate



setrecursionlimit(10 ** 9)

INF = 1 << 60





def input():

    return stdin.readline().strip()





def prime_numbers(n):

    if n < 2:

        return []



    m = (n + 1) // 2

    p = [1] * m

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

        if p[i]:

            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)



    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}





def main():

    N = 10 ** 5

    primes = prime_numbers(N)

    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]

    a = tuple(accumulate(a))



    ans = []

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

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

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



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





if __name__ == "__main__":

    main()

import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10**9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []
    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n**0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (
                ((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1
            )
    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10**5)
    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10**5 + 1)]
    B = [0]
    B.extend(accumulate(A))
    Q, *LR = map(int, read().split())
    ans = [0] * Q
    for i, (l, r) in enumerate(zip(LR[::2], LR[1::2])):
        ans[i] = B[r + 1] - B[l]
    print(*ans, sep="\n")
    return


if __name__ == "__main__":
    main()

from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10**9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []
    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n**0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (
                ((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1
            )
    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


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


if __name__ == "__main__":
    main()

-import sys +from sys import stdin, setrecursionlimit -read = sys.stdin.read -readline = sys.stdin.readline -readlines = sys.stdin.readlines -sys.setrecursionlimit(10**9) +setrecursionlimit(10**9) + + +def input(): +    return stdin.readline().strip() -    primes = prime_numbers(10**5) -    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10**5 + 1)] -    B = [0] -    B.extend(accumulate(A)) -    Q, *LR = map(int, read().split()) -    ans = [0] * Q -    for i, (l, r) in enumerate(zip(LR[::2], LR[1::2])): -        ans[i] = B[r + 1] - B[l] -    print(*ans, sep="\n") -    return +    N = 10**5 +    primes = prime_numbers(N) +    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)] +    a = tuple(accumulate(a)) +    ans = [] +    Q, *LR = list(map(int, open(0).read().split())) +    for l, r in zip(*[iter(LR)] * 2): +        ans.append(a[r] - a[l - 1]) +    print(("\n".join(map(str, ans))))