CodeEff/ECCO huggingface dataset:
# Original solution
from collections import deque
from collections import defaultdict
from collections import Counter
from itertools import permutations

def main():
    Q = int(eval(input()))
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

    for l, r in LR:
        cnt = 0
        for i in range(l, r + 1, 2):
            x = (i + 1) // 2
            if is_prime(i) and is_prime(x):
                cnt += 1
        print(cnt)

def is_prime(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True

main()


# Optimized solution
import bisect

def main():
    Q = int(eval(input()))
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

    l = min(LR)[0]
    r = max(LR, key=lambda x: x[1])[1]
    num = []
    apnd = num.append
    for i in range(l, r + 1, 2):
        x = (i + 1) // 2
        if is_prime(i) and is_prime(x):
            apnd(i)

    for l, r in LR:
        x = bisect.bisect_left(num, l)
        y = bisect.bisect_right(num, r)
        print((y - x))

def is_prime(n):
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True

main()
# Original solution
M = 10**6
p = [1]*M
p[0] = p[1] = 0
for i in range(2, 4*10**4):
    if p[i]:
        for j in range(i*i, M, i):
            p[j] = 0
C = [0]*M
for i in range(2, M):
    if p[i] and p[(i+1)//2]:
        C[i] = C[i-1] + 1
    else:
        C[i] = C[i-1]
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((C[r] - C[l-1]))

# Optimized solution
M = 10**5+1
p = [1]*M
p[0] = p[1] = 0
for i in range(2, 10**3):
    if p[i]:
        for j in range(i*i, M, i):
            p[j] = 0
C = [0]*M
for i in range(2, M):
    if p[i] and p[(i+1)//2]:
        C[i] = C[i-1] + 1
    else:
        C[i] = C[i-1]
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((C[r] - C[l-1]))
# Original solution
from functools import lru_cache
@lru_cache(maxsize=None)
def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

# @lru_cache(maxsize=None)
def like2017(x):
    return is_prime(i) and is_prime((i+1)//2)
    
table=[0,0]
for i in range(2,10**5):
    table+=table[i-1]+like2017(i),
        
n=int(eval(input()))
for _ in range(n):
    a,b=list(map(int,input().split()))
    print((table[b]-table[a-1]))
# print(table)


# Optimized solution
#from functools import lru_cache
#@lru_cache(maxsize=None)
def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

# @lru_cache(maxsize=None)
def like2017(x):
    return is_prime(i) and is_prime((i+1)//2)
    
table=[0,0]
for i in range(2,10**5):
    table+=table[i-1]+like2017(i),
        
n=int(eval(input()))
for _ in range(n):
    a,b=list(map(int,input().split()))
    print((table[b]-table[a-1]))
# print(table)
# Original solution
import sys
import bisect
input = sys.stdin.readline

n = int(eval(input()))
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= len(prime):
        break

cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        cum[i] = cum[i - 1]
      
for x, y in l:
    p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)

# Optimized solution
import sys
import bisect
import math
input = sys.stdin.readline

n = int(eval(input()))
l = [list(map(int, input().split())) for _ in range(n)]

mc = 0
for v in l:
    mc = max(mc, v[1])
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)
# Original solution
def prime(n):
    prime_lst = []
    num_lst = []
    for i in range(2,n+1):
        if i not in num_lst:
            prime_lst.append(i)
            for j in range(i*i, n+1, i):
                #add all the dividers 
                num_lst.append(j)
        #print(prime_lst)
        #print(num_lst)
    return prime_lst
    
    
Q = int(eval(input()))
for i in range(Q):
    x = []
    l,r = list(map(int,input().split()))
    for i in range(l,r+1,2):
        #print(i)
        lst = prime(i)
        if i in lst and (i+1)/2 in lst:
            x.append(i)

    print((len(x)))

# Optimized solution
import math
from itertools import accumulate

def is_prime(n):
    if n == 1:
        return 0
    for k in range(2,int(math.sqrt(n))+1):
        if n % k == 0:
            return 0
    return 1
    
Q = int(eval(input()))    
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L,max_R+ 1):
    if (i%2 ==1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)
    
#print(check)

check = [0] + check
check = list(accumulate(check))
#print(check)
#print(R,L,min_L)

for i in range(Q):
    print((check[R[i]-min_L+1]-check[L[i]-min_L]))
# Original solution
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

Q = int(eval(input()))
A = [0] * 100001 #A[0]からA[100000]までのリスト
A[3] = 1
S = sieve(100000)

for i in range(5,100001,4):
    if i in S and (i+1)/2 in S:
        A[i] = 1
for i in range(4,100001):
    A[i] += A[i-1]

for i in range(Q):
    l, r = list(map(int, input().split()))
    print((A[r]-A[l-1]))


# Optimized solution
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙＝戻り値は各要素が素数のリスト
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

def sieveyn(n): #nまでの素数をエラトステネスの篩で列挙＝戻り値は各要素が素数のリスト
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return s


Q = int(eval(input()))
A = [0] * 100001 #A[0]からA[100000]までのリスト
A[3] = 1
S = sieveyn(100000)

for i in range(5,100001,4):
    if S[i] and S[int((i+1)/2)]:
        A[i] = 1
for i in range(4,100001):
    A[i] += A[i-1]

#print(A[:100])

for i in range(Q):
    l, r = list(map(int, input().split()))
    print((A[r]-A[l-1]))
# Original solution
import math

prime = [2]
max = 10 ** 5
limit = int(math.sqrt(max))
data = [i + 1 for i in range(2, max, 2)]

while limit > data[0]:
    prime.append(data[0])
    data = [j for j in data if j % data[0] != 0]
prime = prime + data

lista = [0] * max
for i in prime:
    if (i + 1) / 2 in prime:
        lista[i - 1] = 1

listb = [0]
for i in range(max):
    listb.append(lista[i] + listb[i])

q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((listb[r] - listb[l - 1]))

# Optimized solution
import math

prime = [2]
max = 10 ** 5
limit = int(math.sqrt(max))
data = [i + 1 for i in range(2, max, 2)]

# エラストテネスの篩
while limit > data[0]:
    prime.append(data[0])
    data = [j for j in data if j % data[0] != 0]
prime = prime + data

# if (i + 1) / 2 in primeのにぶたん
def binary_search_loop(data, target):
    imin = 0
    imax = len(data) - 1
    while imin <= imax:
        imid = imin + (imax - imin) // 2
        if target == data[imid]:
            return True
        elif target < data[imid]:
            imax = imid - 1
        else:
            imin = imid + 1
    return False

# 累積和
lista = [0] * max
for i in prime:
    if binary_search_loop(prime, (i + 1) / 2):
        lista[i - 1] = 1
listb = [0]
for i in range(max):
    listb.append(lista[i] + listb[i])

# rまでの累積 - l - 1までの累積
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((listb[r] - listb[l - 1]))
# Original solution
from itertools import accumulate
def is_prime(n):
   if n == 1:
       return False
   for i in range(2, int(n ** 0.5) + 1):
       if n % i == 0:
           return False
   return True

q = int(eval(input()))

l, r = [],[]
for _ in range(q):
    t, tt = list(map(int, input().split()))
    l.append(t)
    r.append(tt)

m_r = max(r)

table = [0] * (m_r + 2)
for i in range(1, m_r + 1, 2):
    if is_prime(i) and is_prime((i + 1) // 2):
        table[i] = 1

c_table = list(accumulate(table))

for i in range(q):
    print((c_table[r[i]] - c_table[l[i]-1]))

# Optimized solution
from itertools import accumulate

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

q = int(eval(input()))

l, r = [],[]
for _ in range(q):
    t, tt = list(map(int, input().split()))
    l.append(t)
    r.append(tt)

m_r = max(r)

table = [0] * (m_r + 2)
for i in range(1, m_r + 1, 2):
    if is_prime(i) and is_prime((i + 1) // 2):
        table[i] = 1

acc_table = list(accumulate(table))

for i in range(q):
    print((acc_table[r[i]] - acc_table[l[i]-1]))
# Original solution
q = int(eval(input()))
a = [list(map(int, input().split())) for i in range(q)]
s = [0]*(2*10**5+2)
s[3] = 1
for i in range(3, 10**5):
    for j in range(2, int((2*i)**0.5)+2):
        if (i > j and i % j == 0) or (2*i-1) % j == 0:
                b = 0
                break
    else:
        b = 1
    s[2*i-1] = b
S = [0]
for i in range(1, 10**5+1):
    c = S[i-1] + s[i]
    S.append(c)
for i in range(q):
    print((S[a[i][1]] - S[a[i][0]-1]))

# Optimized solution
import math
from itertools import accumulate


def is_prime(n):
    if n == 1:
        return 0

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0

    return 1


Q = int(eval(input()))
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L, max_R+1):
    if (i % 2 == 1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print((check[R[i] - min_L + 1] - check[L[i] - min_L]))
# Original solution
import bisect
from operator import itemgetter

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

rmax = max(lr, key=itemgetter(1))[1]
primes = list(range(rmax+1))
primes [1] = 0

for i in range(2, int(rmax**0.5)+ 2):
    for j in range(2 * i, rmax+1, i):
        primes[j] = 0
primes = [prime for prime in primes[:] if prime!=0]

lst2017 = [x for x in primes if x != 2 and (x+1)//2 in primes]

for l, r in lr:
    nr = bisect.bisect_right(lst2017, r)
    nl = bisect.bisect_left(lst2017, l)
    print((nr - nl))

# Optimized solution
import bisect
from operator import itemgetter

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

rmax = max(lr, key=itemgetter(1))[1]
primes = list(range(rmax+1))
primes [1] = 0

for i in range(2, int(rmax**0.5)+ 2):
    for j in range(2 * i, rmax+1, i):
        primes[j] = 0
primess = [prime for prime in primes[:] if prime!=0]
lst2017 = [x for x in primess if primes[(x+1)//2] != 0]

for l, r in lr:
    nr = bisect.bisect_right(lst2017, r)
    nl = bisect.bisect_left(lst2017, l)
    print((nr - nl))
# Original solution
q = int(eval(input()))
l = [list(map(int,input().split())) for _ in range(q)]

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
sim_sum = [0]*(10**5+1)

for i in range(len(table)):
    if table[i]*2-1 in table:
        sim_sum[table[i]*2-1] += 1
for i in range(1,10**5+1):
    sim_sum[i] += sim_sum[i-1]
for l_ in l:
    print((sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)]))

# Optimized solution
q = int(eval(input()))
l = [list(map(int,input().split())) for _ in range(q)]

def prime_table(n):
    list = [True for _ in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if list[i]:
            j = i*2
            while j<=n:
                list[j] = False
                j += i
    table = [i for i in range(n+1) if list[i] and i>=2]
    return table

table = prime_table(10**5)
table_set = set(table)
sim_sum = [0]*(10**5+1)

for p in table:
    if p*2-1 in table_set:
        sim_sum[p*2-1] += 1
for i in range(1,10**5+1):
    sim_sum[i] += sim_sum[i-1]
for l_ in l:
    print((sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)]))
# Original solution
from bisect import bisect, bisect_left


size = 10 ** 5 + 1

is_prime = [True] * size
is_prime[0] = is_prime[1] = False

# √size まで
for i in range(2, 317):
  j = 2 * i
  while j < size:
    is_prime[j] = False
    j += i

like_numbers = [
  i 
  for i, x in enumerate(is_prime)
  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]

Q = int(eval(input()))

# print(like_numbers[:20])

for _ in range(Q):
  l, r = list(map(int, input().split()))
  if l == r:
    print((1 if l in like_numbers else 0))
  else:
  	print((bisect(like_numbers, r) - bisect_left(like_numbers, l)))  
  

# Optimized solution
from bisect import bisect, bisect_left


size = 10 ** 5 + 1

is_prime = [True] * size
is_prime[0] = is_prime[1] = False

# √size まで
for i in range(2, 317):
  j = 2 * i
  while j < size:
    is_prime[j] = False
    j += i

# 先に like_numbers のテーブルを作っておく    
like_numbers = [
  i 
  for i, x in enumerate(is_prime)
  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]

Q = int(eval(input()))

for _ in range(Q):
  l, r = list(map(int, input().split()))
  # l から r まで探索してると 10^5 かかって間に合わないので二分探索を行う
  print((bisect(like_numbers, r) - bisect_left(like_numbers, l)))
# Original solution
from bisect import bisect, bisect_left


size = 10 ** 5 + 1

is_prime = [True] * size
is_prime[0] = is_prime[1] = False

# √size まで
for i in range(2, 317):
  j = 2 * i
  while j < size:
    is_prime[j] = False
    j += i

# 先に like_numbers のテーブルを作っておく    
like_numbers = [
  i 
  for i, x in enumerate(is_prime)
  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]

Q = int(eval(input()))

for _ in range(Q):
  l, r = list(map(int, input().split()))
  # l から r まで探索してると 10^5 かかって間に合わないので二分探索を行う
  print((bisect(like_numbers, r) - bisect_left(like_numbers, l)))  
  

# Optimized solution
from itertools import count

N = 10 ** 5 + 10

is_prime = [True] * N
is_prime[0] = is_prime[1] = False

# ほぼO(N)
for i in range(N):
  if is_prime[i]:
    for j in count(2 * i, i):
      if j >= N:
        break
      is_prime[j] = False
      
is_2017_like_number = [0] * N

# O(N)
for i in range(N):
  if i % 2 != 0 and is_prime[i] and is_prime[(i + 1) // 2]:
    is_2017_like_number[i] = 1
    
cusum = [0] * (N + 1)

for i in range(N):
  cusum[i + 1] = cusum[i] + is_2017_like_number[i]
  
Q = int(eval(input()))

for _ in range(Q):
  l, r = list(map(int, input().split()))
  r += 1  # 操作しやすいように [l, r) にする
  
  print((cusum[r] - cusum[l]))
# Original solution
import math
def Sieve_of_Eratosthenes(N):
	prime={}
	for i in range(2,N+1):
		prime[i]=1

	for i in range(2,math.ceil(N**0.5)+1):
		tmp=set()
		for j in prime:
			if j>i and j%i==0: tmp.add(j)
		for j in tmp:
			prime.pop(j)

	return prime

N=10**5
prime=Sieve_of_Eratosthenes(N)
a=[0]*(N)
for i in range(2,N):
	if i in prime and (i+1)//2 in prime: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

for i in range(int(eval(input()))):
	l,r=list(map(int,input().split()))
	print((a[r]-a[l-1]))

# Optimized solution
import math
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
 
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

N=10**5
prime=sieve(N)
a=[0]*(N)
for i in range(2,N):
	if prime[i] and prime[(i+1)//2]: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

for i in range(int(eval(input()))):
	l,r=list(map(int,input().split()))
	print((a[r]-a[l-1]))
# Original solution
import math
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
 
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

N=10**5
prime=sieve(N)
a=[0 for i in range(N+1)]
for i in range(3,N):
	if prime[i] and prime[(i+1)//2]: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

Q=int(eval(input()))
for i in range(Q):
	l,r=list(map(int,input().split()))
	print((a[r]-a[l-1]))

# Optimized solution
import sys

def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime

    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False

    return is_prime


def main():
    input = sys.stdin.readline
    Q = int(eval(input()))
    is_prime = sieve(10**5)
    A = [0 for _ in range(10**5 + 1)]
    for i in range(3, 10**5 + 1):
        if is_prime[i] and is_prime[(i+1)//2]:
            A[i] = A[i-1] + 1
        else:
            A[i] = A[i-1]

    for _ in range(Q):
        l, r = list(map(int, input().split()))
        print((A[r] - A[l-1]))


if __name__ == '__main__':
    main()
# Original solution
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)

# Optimized solution
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)
# Original solution
import math
n = 100000
integer = [i for i in range(2,n+1)]
prime = []
while integer[0] <= math.sqrt(n):
    p = integer[0] 
    prime.append(p)
    integer = [i for i in integer if i % p != 0]
prime = prime + integer
like = []
likesum = [0]*(n+1)
for i in range(len(prime)):
    if (prime[i]+1)//2 in prime:
        like.append(prime[i])
for i in range(n):
    if i in like:
        likesum[i+1] = likesum[i] + 1
    else:
        likesum[i+1] = likesum[i]    
q = int(eval(input()))
for i in range(q):
    l,r = list(map(int,input().split()))
    print((likesum[r+1]-likesum[l]))


# Optimized solution
import math
n = 100000
integer = [i for i in range(2,n+1)]
prime = set()
while integer[0] <= math.sqrt(n):
    p = integer[0] 
    prime.add(p)
    integer = [i for i in integer if i % p != 0]
prime = prime | set(integer)
like = set()
likesum = [0]*(n+1)
for i in prime:
    if (i+1)//2 in prime:
        like.add(i)
for i in range(n):
    if i in like:
        likesum[i+1] = likesum[i] + 1
    else:
        likesum[i+1] = likesum[i]    
q = int(eval(input()))
for i in range(q):
    l,r = list(map(int,input().split()))
    print((likesum[r+1]-likesum[l]))
# Original solution
def get_prime(x):
    if x <= 1:
        return []
    prime = [2]
    limit = int(x**0.5)
    
    data = [i + 1 for i in range(2, x, 2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j%data[0] != 0]
    
    return prime + data
    

q=int(eval(input()))
table = get_prime(100000)
for i in range(q):
    l,r = list(map(int,input().split()))
    ans = 0
    for p in range(l,r+1,2):
        if p in table and (p+1)//2 in table:
            ans +=1
    print(ans)          

# Optimized solution
def get_prime(x):
    l = [True] * (x + 1)
    l[0] = False
    l[1] = False
    for i in range(2,int(x**0.5) + 1):
        if not l[i]:
            continue
        for j in range(i * 2, x + 1, i):
            l[j] = False
    return l        
q=int(eval(input()))
table = get_prime(100000)
s=[0]*(100001)

for i in range(100000):
    if table[i] and table[(i+1)//2]:
        s[i] = 1

for i in range(100000):        
    s[i+1] += s[i]

for i in range(q):
    l,r=list(map(int,input().split()))
    print((s[r]-s[l-1]))