import random

import numpy as np



def is_prime(q,k=50):

    if q == 2: return 1

    if q < 2 or q&1 == 0: return 0



    d = (q-1)>>1

    while d&1 == 0:

        d >>= 1

    

    for i in range(k):

        a = random.randint(1,q-1)

        t = d

        y = pow(a,t,q)

        while t != q-1 and y != 1 and y != q-1: 

            y = pow(y,2,q)

            t <<= 1

        if y != q-1 and t&1 == 0:

            return 0

    return 1

  

chk = np.array([0]*10**5)

for i in range(10**5):

  chk[i] = is_prime(i+1,10)

  

ans = np.array([0]*10**5)

for i in range(2,10**5):

  ans[i] = chk[i]&chk[(i+1)//2]

np.cumsum(ans,out=ans)



import sys

input = sys.stdin.readline

q = int(eval(input()))

for i in range(q):

  l,s = list(map(int,input().split()))

  print((ans[s-1]-ans[max(0,l-2)]))
import math

def eratosthenes(limit):

    A = [i for i in range(2, limit+1)]

    P = []

    while True:

        prime = min(A)

        if prime > math.sqrt(limit):

            break

        P.append(prime)

        i = 0

        while i < len(A):

            if A[i] % prime == 0:

                A.pop(i)

                continue

            i += 1

    for a in A:

        P.append(a)

    return list(P)



a = eratosthenes(100000)

b = set([2*i-1 for i in a])

a = set(a)

chk = sorted(list(a&b))



from bisect import bisect,bisect_left

import sys

input = sys.stdin.readline



q = int(eval(input()))

for i in range(q):

  l,r = list(map(int,input().split()))

  print((bisect(chk,r)-bisect_left(chk,l)))
import random
import numpy as np


def is_prime(q, k=50):
    if q == 2:
        return 1
    if q < 2 or q & 1 == 0:
        return 0
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return 0
    return 1


chk = np.array([0] * 10**5)
for i in range(10**5):
    chk[i] = is_prime(i + 1, 10)
ans = np.array([0] * 10**5)
for i in range(2, 10**5):
    ans[i] = chk[i] & chk[(i + 1) // 2]
np.cumsum(ans, out=ans)
import sys

input = sys.stdin.readline
q = int(eval(input()))
for i in range(q):
    l, s = list(map(int, input().split()))
    print((ans[s - 1] - ans[max(0, l - 2)]))

import math


def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    P = []
    while True:
        prime = min(A)
        if prime > math.sqrt(limit):
            break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        P.append(a)
    return list(P)


a = eratosthenes(100000)
b = set([2 * i - 1 for i in a])
a = set(a)
chk = sorted(list(a & b))
from bisect import bisect, bisect_left
import sys

input = sys.stdin.readline
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((bisect(chk, r) - bisect_left(chk, l)))

-import random -import numpy as np +import math -def is_prime(q, k=50): -    if q == 2: -        return 1 -    if q < 2 or q & 1 == 0: -        return 0 -    d = (q - 1) >> 1 -    while d & 1 == 0: -        d >>= 1 -    for i in range(k): -        a = random.randint(1, q - 1) -        t = d -        y = pow(a, t, q) -        while t != q - 1 and y != 1 and y != q - 1: -            y = pow(y, 2, q) -            t <<= 1 -        if y != q - 1 and t & 1 == 0: -            return 0 -    return 1 +def eratosthenes(limit): +    A = [i for i in range(2, limit + 1)] +    P = [] +    while True: +        prime = min(A) +        if prime > math.sqrt(limit): +            break +        P.append(prime) +        i = 0 +        while i < len(A): +            if A[i] % prime == 0: +                A.pop(i) +                continue +            i += 1 +    for a in A: +        P.append(a) +    return list(P) -chk = np.array([0] * 10**5) -for i in range(10**5): -    chk[i] = is_prime(i + 1, 10) -ans = np.array([0] * 10**5) -for i in range(2, 10**5): -    ans[i] = chk[i] & chk[(i + 1) // 2] -np.cumsum(ans, out=ans) +a = eratosthenes(100000) +b = set([2 * i - 1 for i in a]) +a = set(a) +chk = sorted(list(a & b)) +from bisect import bisect, bisect_left -    l, s = list(map(int, input().split())) -    print((ans[s - 1] - ans[max(0, l - 2)])) +    l, r = list(map(int, input().split())) +    print((bisect(chk, r) - bisect_left(chk, l)))