from functools import lru_cache





@lru_cache(maxsize=None)

def is_prime(n):

    """

    nが素数かどうか判定する

    """

    if n < 2:

        return False

    elif n == 2:

        return True

    elif n % 2 == 0:

        return False

    else:

        i = 3

        while i ** 2 <= n:

            if n % i == 0:

                return False

            i += 2

        return True





size = 10 ** 5 + 1

memo = [0] * size

for n in range(3, size):

    memo[n] = memo[n - 1]

    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):

        memo[n] += 1



Q = int(eval(input()))

for _ in range(Q):

    left, right = list(map(int, input().split(' ')))

    print((memo[right] - memo[left - 1]))

size = 10 ** 5 + 1

is_primes = [True] * size

is_primes[0] = False

is_primes[1] = False

for n in range(2, size):

    if not is_primes[n]:

        continue



    m = n * 2

    while m < size:

        is_primes[m] = False

        m += n



dp = [0] * size

for i in range(1, size):

    dp[i] = dp[i - 1]

    if i % 2 == 1 and is_primes[i] and is_primes[(i + 1) // 2]:

        dp[i] += 1



Q = int(eval(input()))

for _ in range(Q):

    left, right = list(map(int, input().split(' ')))

    print((dp[right] - dp[left - 1]))

from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i**2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


size = 10**5 + 1
memo = [0] * size
for n in range(3, size):
    memo[n] = memo[n - 1]
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        memo[n] += 1
Q = int(eval(input()))
for _ in range(Q):
    left, right = list(map(int, input().split(" ")))
    print((memo[right] - memo[left - 1]))

size = 10**5 + 1
is_primes = [True] * size
is_primes[0] = False
is_primes[1] = False
for n in range(2, size):
    if not is_primes[n]:
        continue
    m = n * 2
    while m < size:
        is_primes[m] = False
        m += n
dp = [0] * size
for i in range(1, size):
    dp[i] = dp[i - 1]
    if i % 2 == 1 and is_primes[i] and is_primes[(i + 1) // 2]:
        dp[i] += 1
Q = int(eval(input()))
for _ in range(Q):
    left, right = list(map(int, input().split(" ")))
    print((dp[right] - dp[left - 1]))

-from functools import lru_cache - - -@lru_cache(maxsize=None) -def is_prime(n): -    """ -    nが素数かどうか判定する -    """ -    if n < 2: -        return False -    elif n == 2: -        return True -    elif n % 2 == 0: -        return False -    else: -        i = 3 -        while i**2 <= n: -            if n % i == 0: -                return False -            i += 2 -        return True - - -memo = [0] * size -for n in range(3, size): -    memo[n] = memo[n - 1] -    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2): -        memo[n] += 1 +is_primes = [True] * size +is_primes[0] = False +is_primes[1] = False +for n in range(2, size): +    if not is_primes[n]: +        continue +    m = n * 2 +    while m < size: +        is_primes[m] = False +        m += n +dp = [0] * size +for i in range(1, size): +    dp[i] = dp[i - 1] +    if i % 2 == 1 and is_primes[i] and is_primes[(i + 1) // 2]: +        dp[i] += 1 -    print((memo[right] - memo[left - 1])) +    print((dp[right] - dp[left - 1]))