a=[0 for i in range(10**5+5)]

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

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

        if i%j==0 and j!=i:

            break

    else:

        a[i]=1

a[3],a[2]=1,1

b=[0 for i in range(10**5+5)]

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

    b[i]=a[i] and a[(i+1)//2]

c=[0]

for i in range(len(b)):

    c.append(c[i]+b[i])

for i in range(int(eval(input()))):

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

    print((c[r+1]-c[l]))
a=[0 for i in range(10**5+3)]

b=[1 for i in range(10**5+3)]

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

    if b[i]==1:

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

            b[j]=0

b[0]=0

b[1]=0

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

    a[i]=b[i] and b[(i+1)//2]

e=[a[0]]

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

    e.append(a[i]+e[i-1])

#print(e)

for i in range(int(eval(input()))):

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

    print((e[r]-e[l-1]))
a = [0 for i in range(10**5 + 5)]
for i in range(3, 10**5 + 3, 2):
    for j in range(3, int(i**0.5) + 1, 2):
        if i % j == 0 and j != i:
            break
    else:
        a[i] = 1
a[3], a[2] = 1, 1
b = [0 for i in range(10**5 + 5)]
for i in range(3, 10**5 + 3, 2):
    b[i] = a[i] and a[(i + 1) // 2]
c = [0]
for i in range(len(b)):
    c.append(c[i] + b[i])
for i in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    print((c[r + 1] - c[l]))

a = [0 for i in range(10**5 + 3)]
b = [1 for i in range(10**5 + 3)]
for i in range(2, 10**5 + 3):
    if b[i] == 1:
        for j in range(2 * i, 10**5 + 3, i):
            b[j] = 0
b[0] = 0
b[1] = 0
for i in range(1, 10**5 + 3, 2):
    a[i] = b[i] and b[(i + 1) // 2]
e = [a[0]]
for i in range(1, 10**5 + 3):
    e.append(a[i] + e[i - 1])
# print(e)
for i in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    print((e[r] - e[l - 1]))

-a = [0 for i in range(10**5 + 5)] -for i in range(3, 10**5 + 3, 2): -    for j in range(3, int(i**0.5) + 1, 2): -        if i % j == 0 and j != i: -            break -    else: -        a[i] = 1 -a[3], a[2] = 1, 1 -b = [0 for i in range(10**5 + 5)] -for i in range(3, 10**5 + 3, 2): -    b[i] = a[i] and a[(i + 1) // 2] -c = [0] -for i in range(len(b)): -    c.append(c[i] + b[i]) +a = [0 for i in range(10**5 + 3)] +b = [1 for i in range(10**5 + 3)] +for i in range(2, 10**5 + 3): +    if b[i] == 1: +        for j in range(2 * i, 10**5 + 3, i): +            b[j] = 0 +b[0] = 0 +b[1] = 0 +for i in range(1, 10**5 + 3, 2): +    a[i] = b[i] and b[(i + 1) // 2] +e = [a[0]] +for i in range(1, 10**5 + 3): +    e.append(a[i] + e[i - 1]) +# print(e) -    print((c[r + 1] - c[l])) +    print((e[r] - e[l - 1]))