N = int(eval(input()))

MAX=110000

S = [_+2 for _ in range(MAX)]

old = S

i = 0

while True:

  new = set([])

  t = old[i]

  for j in range(len(old)):

    if old[j] == t or old[j]%t != 0:

      new.add(old[j])

  if len(old) == len(new):

    break

  old = list(new)

  old.sort()

  i += 1





#print(old)

A = [0 for _ in range(MAX)]  

for i in range(MAX):

  if i%2 == 0:

    continue

  if i in new and (i+1)//2 in new:

    A[i] = 1

SUM = [0 for _ in range(MAX)] 

for i in range(1,MAX):

  SUM[i] += A[i]+SUM[i-1]

#print(SUM)



for i in range(N):

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

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

  print(ans)
def get_sieve_of_eratosthenes(n):

    if not isinstance(n, int):

        raise TypeError('n is int type.')

    if n < 2:

        raise ValueError('n is more than 2')

    prime = [2]

    limit = int(n**0.5) #ルートn以上で割れることはない

    data = [i + 1 for i in range(2, n, 2)] #最初から3スタートの奇数にしておく

    while True:

        p = data[0]

        if limit < p: #ここでイコールが入るとlimitが素数の時にlimit^2が残ってダメ。

            return prime + data

        prime.append(p) #ここで一番最初に取り出した素数を加える。

        data = [e for e in data if e % p != 0] #残りでその素数で割れない数字を取得。



MAX = pow(10,5)+10

A = get_sieve_of_eratosthenes(MAX)

A = set(A)

S = [0]

for i in range(1,MAX):

  if i in A and (i+1)%2 == 0 and (i+2)//2 in A:

    temp = S[-1]+1

  else:

    temp = S[-1]

  S.append(temp)

Q = int(eval(input()))

for i in range(Q):

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

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

  print(ans)
N = int(eval(input()))
MAX = 110000
S = [_ + 2 for _ in range(MAX)]
old = S
i = 0
while True:
    new = set([])
    t = old[i]
    for j in range(len(old)):
        if old[j] == t or old[j] % t != 0:
            new.add(old[j])
    if len(old) == len(new):
        break
    old = list(new)
    old.sort()
    i += 1
# print(old)
A = [0 for _ in range(MAX)]
for i in range(MAX):
    if i % 2 == 0:
        continue
    if i in new and (i + 1) // 2 in new:
        A[i] = 1
SUM = [0 for _ in range(MAX)]
for i in range(1, MAX):
    SUM[i] += A[i] + SUM[i - 1]
# print(SUM)
for i in range(N):
    l, r = list(map(int, input().split()))
    ans = SUM[r] - SUM[l - 1]
    print(ans)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int type.")
    if n < 2:
        raise ValueError("n is more than 2")
    prime = [2]
    limit = int(n**0.5)  # ルートn以上で割れることはない
    data = [i + 1 for i in range(2, n, 2)]  # 最初から3スタートの奇数にしておく
    while True:
        p = data[0]
        if limit < p:  # ここでイコールが入るとlimitが素数の時にlimit^2が残ってダメ。
            return prime + data
        prime.append(p)  # ここで一番最初に取り出した素数を加える。
        data = [e for e in data if e % p != 0]  # 残りでその素数で割れない数字を取得。


MAX = pow(10, 5) + 10
A = get_sieve_of_eratosthenes(MAX)
A = set(A)
S = [0]
for i in range(1, MAX):
    if i in A and (i + 1) % 2 == 0 and (i + 2) // 2 in A:
        temp = S[-1] + 1
    else:
        temp = S[-1]
    S.append(temp)
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    ans = S[r] - S[l - 1]
    print(ans)

-N = int(eval(input())) -MAX = 110000 -S = [_ + 2 for _ in range(MAX)] -old = S -i = 0 -while True: -    new = set([]) -    t = old[i] -    for j in range(len(old)): -        if old[j] == t or old[j] % t != 0: -            new.add(old[j]) -    if len(old) == len(new): -        break -    old = list(new) -    old.sort() -    i += 1 -# print(old) -A = [0 for _ in range(MAX)] -for i in range(MAX): -    if i % 2 == 0: -        continue -    if i in new and (i + 1) // 2 in new: -        A[i] = 1 -SUM = [0 for _ in range(MAX)] +def get_sieve_of_eratosthenes(n): +    if not isinstance(n, int): +        raise TypeError("n is int type.") +    if n < 2: +        raise ValueError("n is more than 2") +    prime = [2] +    limit = int(n**0.5)  # ルートn以上で割れることはない +    data = [i + 1 for i in range(2, n, 2)]  # 最初から3スタートの奇数にしておく +    while True: +        p = data[0] +        if limit < p:  # ここでイコールが入るとlimitが素数の時にlimit^2が残ってダメ。 +            return prime + data +        prime.append(p)  # ここで一番最初に取り出した素数を加える。 +        data = [e for e in data if e % p != 0]  # 残りでその素数で割れない数字を取得。 + + +MAX = pow(10, 5) + 10 +A = get_sieve_of_eratosthenes(MAX) +A = set(A) +S = [0] -    SUM[i] += A[i] + SUM[i - 1] -# print(SUM) -for i in range(N): +    if i in A and (i + 1) % 2 == 0 and (i + 2) // 2 in A: +        temp = S[-1] + 1 +    else: +        temp = S[-1] +    S.append(temp) +Q = int(eval(input())) +for i in range(Q): -    ans = SUM[r] - SUM[l - 1] +    ans = S[r] - S[l - 1]