# ABC084D - 2017-like Number

import sys

input = sys.stdin.readline



from bisect import bisect_left, bisect_right





def get_primes(n):

    # return a list of primes <= n

    n += 1  # include n itself

    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 = int(input())

    A = tuple(tuple(map(int, input().split())) for _ in range(Q))

    _, R = zip(*A)

    lim = max(R)

    P = get_primes(lim)

    S = set(P)

    selected_P = [p for p in P if (p + 1) // 2 in S]

    ans = []

    for l, r in A:

        x = bisect_right(selected_P, r) - bisect_left(selected_P, l)

        ans += [x]

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





if __name__ == "__main__":

    main()

# ABC084D - 2017-like Number

import sys

input = sys.stdin.readline



from bisect import bisect_left, bisect_right





def get_primes(n: int) -> list:

    # return a list of primes <= n

    n += 1  # include n itself

    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 = int(input())

    A = tuple(tuple(map(int, input().split())) for _ in range(Q))

    P = get_primes(10 ** 5)

    S = set(P)

    selected_P = [p for p in P if (p + 1) // 2 in S]

    ans = []

    bsr, bsl = bisect_right, bisect_left

    for l, r in A:

        x = bsr(selected_P, r) - bsl(selected_P, l)

        ans += [x]

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





if __name__ == "__main__":

    main()

# ABC084D - 2017-like Number
import sys

input = sys.stdin.readline
from bisect import bisect_left, bisect_right


def get_primes(n):
    # return a list of primes <= n
    n += 1  # include n itself
    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 = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    _, R = zip(*A)
    lim = max(R)
    P = get_primes(lim)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    ans = []
    for l, r in A:
        x = bisect_right(selected_P, r) - bisect_left(selected_P, l)
        ans += [x]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

# ABC084D - 2017-like Number
import sys

input = sys.stdin.readline
from bisect import bisect_left, bisect_right


def get_primes(n: int) -> list:
    # return a list of primes <= n
    n += 1  # include n itself
    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 = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(Q))
    P = get_primes(10**5)
    S = set(P)
    selected_P = [p for p in P if (p + 1) // 2 in S]
    ans = []
    bsr, bsl = bisect_right, bisect_left
    for l, r in A:
        x = bsr(selected_P, r) - bsl(selected_P, l)
        ans += [x]
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

-def get_primes(n): +def get_primes(n: int) -> list: -    _, R = zip(*A) -    lim = max(R) -    P = get_primes(lim) +    P = get_primes(10**5) +    bsr, bsl = bisect_right, bisect_left -        x = bisect_right(selected_P, r) - bisect_left(selected_P, l) +        x = bsr(selected_P, r) - bsl(selected_P, l)