import bisect



def PN(N):

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

        if N%i==0:

            return False

    return True



N=[3]

for i in range(5,100001,2):

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

        N.append(i)



Q=int(eval(input()))



for i in range(Q):

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

    ln1=bisect.bisect_left(N,l)

    ln2=bisect.bisect_right(N,l)

    rn1=bisect.bisect_left(N,r)

    rn2=bisect.bisect_right(N,r)

    if ln1==ln2 and rn1==rn2:

        print((rn1-ln1))

    elif ln1==ln2 or rn1==rn2:

        print((rn1-ln2+1))

    else:

        print((rn1-ln2+2))







def PrimeNumber(N):

    f=[1]*(N+1)

    f[0]=0

    f[1]=0



    for i in range(2,N+1):

        if f[i]==0:

            continue

        j = 2

        temp = i

        while temp * j <= N:

            f[temp*j]=0

            j += 1



    return f



PN=PrimeNumber(100000)

C=[0]*100001



C[1]=0



for i in range(2,100001):

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

        C[i]=C[i-1]+1

    else:

        C[i]=C[i-1]



Q=int(eval(input()))



for i in range(Q):

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

    print((C[r]-C[l-1]))
import bisect


def PN(N):
    for i in range(2, int(N**0.5) + 1):
        if N % i == 0:
            return False
    return True


N = [3]
for i in range(5, 100001, 2):
    if PN(i) and PN((i + 1) // 2):
        N.append(i)
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    ln1 = bisect.bisect_left(N, l)
    ln2 = bisect.bisect_right(N, l)
    rn1 = bisect.bisect_left(N, r)
    rn2 = bisect.bisect_right(N, r)
    if ln1 == ln2 and rn1 == rn2:
        print((rn1 - ln1))
    elif ln1 == ln2 or rn1 == rn2:
        print((rn1 - ln2 + 1))
    else:
        print((rn1 - ln2 + 2))

def PrimeNumber(N):
    f = [1] * (N + 1)
    f[0] = 0
    f[1] = 0
    for i in range(2, N + 1):
        if f[i] == 0:
            continue
        j = 2
        temp = i
        while temp * j <= N:
            f[temp * j] = 0
            j += 1
    return f


PN = PrimeNumber(100000)
C = [0] * 100001
C[1] = 0
for i in range(2, 100001):
    if PN[i] == 1 and PN[(i + 1) // 2] == 1:
        C[i] = C[i - 1] + 1
    else:
        C[i] = C[i - 1]
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((C[r] - C[l - 1]))

-import bisect +def PrimeNumber(N): +    f = [1] * (N + 1) +    f[0] = 0 +    f[1] = 0 +    for i in range(2, N + 1): +        if f[i] == 0: +            continue +        j = 2 +        temp = i +        while temp * j <= N: +            f[temp * j] = 0 +            j += 1 +    return f -def PN(N): -    for i in range(2, int(N**0.5) + 1): -        if N % i == 0: -            return False -    return True - - -N = [3] -for i in range(5, 100001, 2): -    if PN(i) and PN((i + 1) // 2): -        N.append(i) +PN = PrimeNumber(100000) +C = [0] * 100001 +C[1] = 0 +for i in range(2, 100001): +    if PN[i] == 1 and PN[(i + 1) // 2] == 1: +        C[i] = C[i - 1] + 1 +    else: +        C[i] = C[i - 1] -    ln1 = bisect.bisect_left(N, l) -    ln2 = bisect.bisect_right(N, l) -    rn1 = bisect.bisect_left(N, r) -    rn2 = bisect.bisect_right(N, r) -    if ln1 == ln2 and rn1 == rn2: -        print((rn1 - ln1)) -    elif ln1 == ln2 or rn1 == rn2: -        print((rn1 - ln2 + 1)) -    else: -        print((rn1 - ln2 + 2)) +    print((C[r] - C[l - 1]))