# coding: utf-8

# Your code here!

U=10**5

is_prime=[True]*(U+1)

is_prime[0]=False

is_prime[1]=False

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

    if p*p>U:

        break

    if is_prime[p]:

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

            is_prime[j]=False



is_2017like=[0]*(U+1)

for p in range(1,U+1):

    if (p+1)//2>U:

        break

    tmp=(is_prime[p] and is_prime[(p+1)//2])

    is_2017like[p]=is_2017like[p-1]+tmp

    

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

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

    ans=is_2017like[r]-is_2017like[l-1]

    print(ans)

def like2017(x):

  if isprime[x]:

    if isprime[(x+1)//2]:

      return True

  return False



n=108000

isprime=[True]*(n+1)

isprime[0]=isprime[1]=False

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

  if isprime[i]:

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

      isprime[j]=False

cum=[]

cum.append(like2017(0))

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

  tmp=0

  if isprime[i]:

    if isprime[(i+1)//2]:

      tmp=1

  cum.append(cum[-1]+tmp)

#print(cum)

q=int(eval(input()))

for _ in range(q):

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

  print((cum[r]-cum[l-1]))

  
# coding: utf-8
# Your code here!
U = 10**5
is_prime = [True] * (U + 1)
is_prime[0] = False
is_prime[1] = False
for p in range(2, U + 1):
    if p * p > U:
        break
    if is_prime[p]:
        for j in range(p * p, U + 1, p):
            is_prime[j] = False
is_2017like = [0] * (U + 1)
for p in range(1, U + 1):
    if (p + 1) // 2 > U:
        break
    tmp = is_prime[p] and is_prime[(p + 1) // 2]
    is_2017like[p] = is_2017like[p - 1] + tmp
for i in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    ans = is_2017like[r] - is_2017like[l - 1]
    print(ans)

def like2017(x):
    if isprime[x]:
        if isprime[(x + 1) // 2]:
            return True
    return False


n = 108000
isprime = [True] * (n + 1)
isprime[0] = isprime[1] = False
for i in range(2, n + 1):
    if isprime[i]:
        for j in range(i * i, n + 1, i):
            isprime[j] = False
cum = []
cum.append(like2017(0))
for i in range(1, n + 1):
    tmp = 0
    if isprime[i]:
        if isprime[(i + 1) // 2]:
            tmp = 1
    cum.append(cum[-1] + tmp)
# print(cum)
q = int(eval(input()))
for _ in range(q):
    l, r = list(map(int, input().split()))
    print((cum[r] - cum[l - 1]))

-# coding: utf-8 -# Your code here! -U = 10**5 -is_prime = [True] * (U + 1) -is_prime[0] = False -is_prime[1] = False -for p in range(2, U + 1): -    if p * p > U: -        break -    if is_prime[p]: -        for j in range(p * p, U + 1, p): -            is_prime[j] = False -is_2017like = [0] * (U + 1) -for p in range(1, U + 1): -    if (p + 1) // 2 > U: -        break -    tmp = is_prime[p] and is_prime[(p + 1) // 2] -    is_2017like[p] = is_2017like[p - 1] + tmp -for i in range(int(eval(input()))): +def like2017(x): +    if isprime[x]: +        if isprime[(x + 1) // 2]: +            return True +    return False + + +n = 108000 +isprime = [True] * (n + 1) +isprime[0] = isprime[1] = False +for i in range(2, n + 1): +    if isprime[i]: +        for j in range(i * i, n + 1, i): +            isprime[j] = False +cum = [] +cum.append(like2017(0)) +for i in range(1, n + 1): +    tmp = 0 +    if isprime[i]: +        if isprime[(i + 1) // 2]: +            tmp = 1 +    cum.append(cum[-1] + tmp) +# print(cum) +q = int(eval(input())) +for _ in range(q): -    ans = is_2017like[r] - is_2017like[l - 1] -    print(ans) +    print((cum[r] - cum[l - 1]))