n=10**5

p=[0,0]+[1]*~-n

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

  if not p[i]:continue

  for j in range(i*2,n+1,i):p[j]=0

c=[0]

for i in range(1,n+1):

  c.append(c[-1]+(i%2and p[i]and p[-~i//2]))

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

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

  print((c[r]-c[l-1]))
n=10**5;p=[0,0]+[1]*~-n

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

 if p[i]:

  for j in range(i*2,n+1,i):p[j]=0

c=[0]

for i in range(1,n+1):c.append(c[-1]+(i%2and p[i]and p[-~i//2]))

for _ in[0]*int(eval(input())):l,r=list(map(int,input().split()));print((c[r]-c[l-1]))
n = 10**5
p = [0, 0] + [1] * ~-n
for i in range(2, int(n**0.5) + 1):
    if not p[i]:
        continue
    for j in range(i * 2, n + 1, i):
        p[j] = 0
c = [0]
for i in range(1, n + 1):
    c.append(c[-1] + (i % 2 and p[i] and p[-~i // 2]))
for _ in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    print((c[r] - c[l - 1]))

n = 10**5
p = [0, 0] + [1] * ~-n
for i in range(2, int(n**0.5) + 1):
    if p[i]:
        for j in range(i * 2, n + 1, i):
            p[j] = 0
c = [0]
for i in range(1, n + 1):
    c.append(c[-1] + (i % 2 and p[i] and p[-~i // 2]))
for _ in [0] * int(eval(input())):
    l, r = list(map(int, input().split()))
    print((c[r] - c[l - 1]))

-    if not p[i]: -        continue -    for j in range(i * 2, n + 1, i): -        p[j] = 0 +    if p[i]: +        for j in range(i * 2, n + 1, i): +            p[j] = 0 -for _ in range(int(eval(input()))): +for _ in [0] * int(eval(input())):