import sys

import bisect

from functools import lru_cache



input = sys.stdin.readline





@lru_cache(maxsize=None)

def is_prime(n):

    if n == 1:

        return False

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

        if n % i == 0:

            return False

    return True





def main():

    Q = int(eval(input()))

    lr = [[int(x) for x in input().split()] for _ in range(Q)]



    sosu = []

    for i in range(1, 10 ** 5 + 1):

        if is_prime(i) and is_prime((i + 1) // 2):

            sosu.append(i)



    for l, r in lr:

        li = bisect.bisect_left(sosu, l)

        ri = bisect.bisect_right(sosu, r)

        print((ri - li))



















if __name__ == '__main__':

    main()

import sys

import bisect



input = sys.stdin.readline





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

    lr = [[int(x) for x in input().split()] for _ in range(Q)]



    P = get_primes(10 ** 5 + 1)

    setP = set(P)

    like = []

    for p in P:

        if (p + 1) // 2 in setP:

            like.append(p)





    for l, r in lr:

        li = bisect.bisect_left(like, l)

        ri = bisect.bisect_right(like, r)

        print((ri - li))





if __name__ == '__main__':

    main()

import sys
import bisect
from functools import lru_cache

input = sys.stdin.readline


@lru_cache(maxsize=None)
def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True


def main():
    Q = int(eval(input()))
    lr = [[int(x) for x in input().split()] for _ in range(Q)]
    sosu = []
    for i in range(1, 10**5 + 1):
        if is_prime(i) and is_prime((i + 1) // 2):
            sosu.append(i)
    for l, r in lr:
        li = bisect.bisect_left(sosu, l)
        ri = bisect.bisect_right(sosu, r)
        print((ri - li))


if __name__ == "__main__":
    main()

import sys
import bisect

input = sys.stdin.readline


def get_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 = int(eval(input()))
    lr = [[int(x) for x in input().split()] for _ in range(Q)]
    P = get_primes(10**5 + 1)
    setP = set(P)
    like = []
    for p in P:
        if (p + 1) // 2 in setP:
            like.append(p)
    for l, r in lr:
        li = bisect.bisect_left(like, l)
        ri = bisect.bisect_right(like, r)
        print((ri - li))


if __name__ == "__main__":
    main()

-from functools import lru_cache -@lru_cache(maxsize=None) -def is_prime(n): -    if n == 1: -        return False -    for i in range(2, int(n**0.5) + 1): -        if n % i == 0: -            return False -    return True +def get_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]] -    sosu = [] -    for i in range(1, 10**5 + 1): -        if is_prime(i) and is_prime((i + 1) // 2): -            sosu.append(i) +    P = get_primes(10**5 + 1) +    setP = set(P) +    like = [] +    for p in P: +        if (p + 1) // 2 in setP: +            like.append(p) -        li = bisect.bisect_left(sosu, l) -        ri = bisect.bisect_right(sosu, r) +        li = bisect.bisect_left(like, l) +        ri = bisect.bisect_right(like, r)