#!/usr/bin/env python3

# coding=utf-8



import sys



import numpy as np



num_max = 100000

primes = np.asarray([True for _ in range(num_max + 1)])

for i in range(num_max + 1):

    if i == 0 or i == 1:

        primes[i] = False

    elif primes[i]:

        primes[i * 2::i] = False

primes = set(np.arange(num_max + 1)[primes])

like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]

cumsum = np.cumsum(like2017)



q = int(sys.stdin.readline().strip())

for _ in range(q):

    l, r = sys.stdin.readline().strip().split(" ")

    l = int(l)

    r = int(r)

    print((cumsum[r] - cumsum[l - 1]))

import numpy as np





def solve(string):

    num_max = 100000

    primes = np.asarray([True for _ in range(num_max + 1)])

    for i in range(num_max + 1):

        if i == 0 or i == 1:

            primes[i] = False

        elif primes[i]:

            primes[i * 2::i] = False

    primes = set(np.arange(num_max + 1)[primes])

    like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]

    cumsum = np.cumsum(like2017)



    q, *lr = list(map(int, string.split()))

    return "\n".join([str(cumsum[r] - cumsum[l - 1]) for l, r in zip(lr[::2], lr[1::2])])





if __name__ == '__main__':

    n = int(eval(input()))

    print((solve('{}\n'.format(n) + '\n'.join([eval(input()) for _ in range(n)]))))

#!/usr/bin/env python3
# coding=utf-8
import sys
import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    elif primes[i]:
        primes[i * 2 :: i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [
    1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)
]
cumsum = np.cumsum(like2017)
q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print((cumsum[r] - cumsum[l - 1]))

import numpy as np


def solve(string):
    num_max = 100000
    primes = np.asarray([True for _ in range(num_max + 1)])
    for i in range(num_max + 1):
        if i == 0 or i == 1:
            primes[i] = False
        elif primes[i]:
            primes[i * 2 :: i] = False
    primes = set(np.arange(num_max + 1)[primes])
    like2017 = [
        1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)
    ]
    cumsum = np.cumsum(like2017)
    q, *lr = list(map(int, string.split()))
    return "\n".join(
        [str(cumsum[r] - cumsum[l - 1]) for l, r in zip(lr[::2], lr[1::2])]
    )


if __name__ == "__main__":
    n = int(eval(input()))
    print((solve("{}\n".format(n) + "\n".join([eval(input()) for _ in range(n)]))))

-#!/usr/bin/env python3 -# coding=utf-8 -import sys -num_max = 100000 -primes = np.asarray([True for _ in range(num_max + 1)]) -for i in range(num_max + 1): -    if i == 0 or i == 1: -        primes[i] = False -    elif primes[i]: -        primes[i * 2 :: i] = False -primes = set(np.arange(num_max + 1)[primes]) -like2017 = [ -    1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1) -] -cumsum = np.cumsum(like2017) -q = int(sys.stdin.readline().strip()) -for _ in range(q): -    l, r = sys.stdin.readline().strip().split(" ") -    l = int(l) -    r = int(r) -    print((cumsum[r] - cumsum[l - 1])) + +def solve(string): +    num_max = 100000 +    primes = np.asarray([True for _ in range(num_max + 1)]) +    for i in range(num_max + 1): +        if i == 0 or i == 1: +            primes[i] = False +        elif primes[i]: +            primes[i * 2 :: i] = False +    primes = set(np.arange(num_max + 1)[primes]) +    like2017 = [ +        1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1) +    ] +    cumsum = np.cumsum(like2017) +    q, *lr = list(map(int, string.split())) +    return "\n".join( +        [str(cumsum[r] - cumsum[l - 1]) for l, r in zip(lr[::2], lr[1::2])] +    ) + + +if __name__ == "__main__": +    n = int(eval(input())) +    print((solve("{}\n".format(n) + "\n".join([eval(input()) for _ in range(n)]))))