# -*- coding:utf-8 -*-

import math





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 = []

    limit = math.sqrt(n)

    data = [i + 1 for i in range(1, n)]

    while True:

        p = data[0]

        if limit <= p:

            return prime + data

        prime.append(p)

        data = [e for e in data if e % p != 0]





if __name__ == '__main__':

    data = get_sieve_of_eratosthenes(100001)

    #print(data[:10])

    

    cnt=len(data)

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

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

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

    for d in data:

      SS[d]=1

    for i in range(3,len(S)):

      if SS[i] and SS[(i+1)//2]: S[i]=1

    for i in range(len(T)):

      T[i]=cnt

      cnt-=S[i]

    #print(T[:10])

    

    Q=int(eval(input()))

    for i in range(Q):

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

      print((T[l]-T[r]+S[r]))
Q = int(eval(input()))

LR = [list(map(int, input().split())) for _ in range(Q)]



SIZE = 10 ** 5

P = [-1] * (SIZE + 1)

P[0], P[1] = 0, 0



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

  if P[i] == -1:

    P[i] = 1

    k = 2

    while i * k <= SIZE:

      P[i * k] = 0

      k += 1

      

PP = [0] * (SIZE + 1)

for i in range(3, SIZE + 1):

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

    PP[i] = 1

#print(PP)



Acum = [0]

for i in range(SIZE + 1):

  Acum.append(Acum[-1] + PP[i])

#print(Acum)



for l, r in LR:

  print((Acum[r + 1] - Acum[l]))

  
# -*- coding:utf-8 -*-
import math


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 = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


if __name__ == "__main__":
    data = get_sieve_of_eratosthenes(100001)
    # print(data[:10])
    cnt = len(data)
    SS = [0] * (10**5 + 1)
    S = [0] * (10**5 + 1)
    T = [0] * (10**5 + 1)
    for d in data:
        SS[d] = 1
    for i in range(3, len(S)):
        if SS[i] and SS[(i + 1) // 2]:
            S[i] = 1
    for i in range(len(T)):
        T[i] = cnt
        cnt -= S[i]
    # print(T[:10])
    Q = int(eval(input()))
    for i in range(Q):
        l, r = list(map(int, input().split()))
        print((T[l] - T[r] + S[r]))

Q = int(eval(input()))
LR = [list(map(int, input().split())) for _ in range(Q)]
SIZE = 10**5
P = [-1] * (SIZE + 1)
P[0], P[1] = 0, 0
for i in range(2, SIZE + 1):
    if P[i] == -1:
        P[i] = 1
        k = 2
        while i * k <= SIZE:
            P[i * k] = 0
            k += 1
PP = [0] * (SIZE + 1)
for i in range(3, SIZE + 1):
    if P[i] and P[(i + 1) // 2]:
        PP[i] = 1
# print(PP)
Acum = [0]
for i in range(SIZE + 1):
    Acum.append(Acum[-1] + PP[i])
# print(Acum)
for l, r in LR:
    print((Acum[r + 1] - Acum[l]))

-# -*- coding:utf-8 -*- -import math - - -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 = [] -    limit = math.sqrt(n) -    data = [i + 1 for i in range(1, n)] -    while True: -        p = data[0] -        if limit <= p: -            return prime + data -        prime.append(p) -        data = [e for e in data if e % p != 0] - - -if __name__ == "__main__": -    data = get_sieve_of_eratosthenes(100001) -    # print(data[:10]) -    cnt = len(data) -    SS = [0] * (10**5 + 1) -    S = [0] * (10**5 + 1) -    T = [0] * (10**5 + 1) -    for d in data: -        SS[d] = 1 -    for i in range(3, len(S)): -        if SS[i] and SS[(i + 1) // 2]: -            S[i] = 1 -    for i in range(len(T)): -        T[i] = cnt -        cnt -= S[i] -    # print(T[:10]) -    Q = int(eval(input())) -    for i in range(Q): -        l, r = list(map(int, input().split())) -        print((T[l] - T[r] + S[r])) +Q = int(eval(input())) +LR = [list(map(int, input().split())) for _ in range(Q)] +SIZE = 10**5 +P = [-1] * (SIZE + 1) +P[0], P[1] = 0, 0 +for i in range(2, SIZE + 1): +    if P[i] == -1: +        P[i] = 1 +        k = 2 +        while i * k <= SIZE: +            P[i * k] = 0 +            k += 1 +PP = [0] * (SIZE + 1) +for i in range(3, SIZE + 1): +    if P[i] and P[(i + 1) // 2]: +        PP[i] = 1 +# print(PP) +Acum = [0] +for i in range(SIZE + 1): +    Acum.append(Acum[-1] + PP[i]) +# print(Acum) +for l, r in LR: +    print((Acum[r + 1] - Acum[l]))