q = int(input())





def is_prime(x):

    if x == 1:

        return False

    d = 2

    while d**2 <= x:

        if x % d == 0:

            return False

        d += 1

    else:

        return True



primes = []

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

    if is_prime(x):

        primes.append(x)

        

A = [0]*(10**5+1)

for prime in primes:

    if is_prime((prime+1)//2):

        A[prime] = 1





S = [0]*(10**5+1)

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

    S[i] = S[i-1]+A[i]





ans = []

for _ in range(q):

    L, R = map(int, input().split())

    cnt = S[R]-S[L-1]

    ans.append(cnt)



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

U = 10**5

is_prime = [1]*(U+1)

is_prime[0] = 0

is_prime[1] = 0

for p in range(2, int(U**.5)+1):

    if is_prime[p]:

        for q in range(2*p, U+1, p):

            is_prime[q] = 0



primes = [p for p, tf in enumerate(is_prime) if tf]





A = [0]*(10**5+1)

for prime in primes:

    if is_prime[(prime+1)//2]:

        A[prime] = 1





S = [0]*(10**5+1)

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

    S[i] = S[i-1]+A[i]





q = int(eval(input()))

for _ in range(q):

    L, R = list(map(int, input().split()))

    ans = S[R]-S[L-1]

    print(ans)
q = int(input())


def is_prime(x):
    if x == 1:
        return False
    d = 2
    while d**2 <= x:
        if x % d == 0:
            return False
        d += 1
    else:
        return True


primes = []
for x in range(2, 10**5 + 1):
    if is_prime(x):
        primes.append(x)
A = [0] * (10**5 + 1)
for prime in primes:
    if is_prime((prime + 1) // 2):
        A[prime] = 1
S = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    S[i] = S[i - 1] + A[i]
ans = []
for _ in range(q):
    L, R = map(int, input().split())
    cnt = S[R] - S[L - 1]
    ans.append(cnt)
print(*ans, sep="\n")

U = 10**5
is_prime = [1] * (U + 1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**0.5) + 1):
    if is_prime[p]:
        for q in range(2 * p, U + 1, p):
            is_prime[q] = 0
primes = [p for p, tf in enumerate(is_prime) if tf]
A = [0] * (10**5 + 1)
for prime in primes:
    if is_prime[(prime + 1) // 2]:
        A[prime] = 1
S = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    S[i] = S[i - 1] + A[i]
q = int(eval(input()))
for _ in range(q):
    L, R = list(map(int, input().split()))
    ans = S[R] - S[L - 1]
    print(ans)

-q = int(input()) - - -def is_prime(x): -    if x == 1: -        return False -    d = 2 -    while d**2 <= x: -        if x % d == 0: -            return False -        d += 1 -    else: -        return True - - -primes = [] -for x in range(2, 10**5 + 1): -    if is_prime(x): -        primes.append(x) +U = 10**5 +is_prime = [1] * (U + 1) +is_prime[0] = 0 +is_prime[1] = 0 +for p in range(2, int(U**0.5) + 1): +    if is_prime[p]: +        for q in range(2 * p, U + 1, p): +            is_prime[q] = 0 +primes = [p for p, tf in enumerate(is_prime) if tf] -    if is_prime((prime + 1) // 2): +    if is_prime[(prime + 1) // 2]: -ans = [] +q = int(eval(input())) -    L, R = map(int, input().split()) -    cnt = S[R] - S[L - 1] -    ans.append(cnt) -print(*ans, sep="\n") +    L, R = list(map(int, input().split())) +    ans = S[R] - S[L - 1] +    print(ans)