Q=int(eval(input()))



def isPrime(x):

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

    if x%i==0:

      return False

  else:

    return True



plist=[False]*(10**5+3)

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

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

    plist[i]=True

#print(plist[:10])



slist=[0]*(10**5+3)

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

  if plist[i]:

    slist[i]=slist[i-1]+1

  else:

    slist[i]=slist[i-1]

#print(slist[:10])

  

for i in range(Q):

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

  print((slist[r]-slist[l-1]))
Q=int(eval(input()))



def prime_sieve(n):

  prime_list=[True]*n

  prime_list[0]=False

  prime_list[1]=False

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

    if not prime_list[i]:

      continue

    else:

      for j in range(i**2,n,i):

        prime_list[j]=False

  

  return prime_list

  #return [i for i in range(n) if is_prime_list[i]]



prime_list=prime_sieve(10**5+1)

#print(prime_list[:10])

  

plist=[0]*(10**5+1)

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

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

    plist[i]=1

#print(plist[:10])



slist=[0]*(10**5+1)

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

  slist[i]=plist[i]+slist[i-1]

#print(slist[:10])

  

for i in range(Q):

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

  print((slist[r]-slist[l-1]))
Q = int(eval(input()))


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


plist = [False] * (10**5 + 3)
for i in range(3, 10**5 + 3, 2):
    if isPrime(i) and isPrime((i + 1) // 2):
        plist[i] = True
# print(plist[:10])
slist = [0] * (10**5 + 3)
for i in range(3, 10**5 + 3):
    if plist[i]:
        slist[i] = slist[i - 1] + 1
    else:
        slist[i] = slist[i - 1]
# print(slist[:10])
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((slist[r] - slist[l - 1]))

Q = int(eval(input()))


def prime_sieve(n):
    prime_list = [True] * n
    prime_list[0] = False
    prime_list[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not prime_list[i]:
            continue
        else:
            for j in range(i**2, n, i):
                prime_list[j] = False
    return prime_list
    # return [i for i in range(n) if is_prime_list[i]]


prime_list = prime_sieve(10**5 + 1)
# print(prime_list[:10])
plist = [0] * (10**5 + 1)
for i in range(3, 10**5 + 1, 2):
    if prime_list[i] and prime_list[(i + 1) // 2]:
        plist[i] = 1
# print(plist[:10])
slist = [0] * (10**5 + 1)
for i in range(3, 10**5 + 1):
    slist[i] = plist[i] + slist[i - 1]
# print(slist[:10])
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((slist[r] - slist[l - 1]))

-def isPrime(x): -    for i in range(2, int(x**0.5) + 1): -        if x % i == 0: -            return False -    else: -        return True +def prime_sieve(n): +    prime_list = [True] * n +    prime_list[0] = False +    prime_list[1] = False +    for i in range(2, int(n**0.5) + 1): +        if not prime_list[i]: +            continue +        else: +            for j in range(i**2, n, i): +                prime_list[j] = False +    return prime_list +    # return [i for i in range(n) if is_prime_list[i]] -plist = [False] * (10**5 + 3) -for i in range(3, 10**5 + 3, 2): -    if isPrime(i) and isPrime((i + 1) // 2): -        plist[i] = True +prime_list = prime_sieve(10**5 + 1) +# print(prime_list[:10]) +plist = [0] * (10**5 + 1) +for i in range(3, 10**5 + 1, 2): +    if prime_list[i] and prime_list[(i + 1) // 2]: +        plist[i] = 1 -slist = [0] * (10**5 + 3) -for i in range(3, 10**5 + 3): -    if plist[i]: -        slist[i] = slist[i - 1] + 1 -    else: -        slist[i] = slist[i - 1] +slist = [0] * (10**5 + 1) +for i in range(3, 10**5 + 1): +    slist[i] = plist[i] + slist[i - 1]