CodeEff/ECCO huggingface dataset:
# Original solution
from bisect import bisect_left


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def is_similar(n):
    pos = bisect_left(p, n)
    if pos < len(p) and p[pos] == n:
        return True
    else:
        return False


q = int(eval(input()))

p = primes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if is_similar(i) and is_similar((i+1)//2):
        l[i] += 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

res = []
for _ in range(q):
    l, r = list(map(int, input().split()))
    res.append(sum_l[r] - sum_l[l-1])

for v in res:
    print(v)

# Optimized solution
from bisect import bisect_left


def eratosthenes(n):
    is_prime = [True] * (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


q = int(eval(input()))

p = eratosthenes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if p[i] and p[(i+1)//2]:
        l[i] = 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

res = []
for _ in range(q):
    l, r = list(map(int, input().split()))
    res.append(sum_l[r] - sum_l[l-1])

for v in res:
    print(v)
# Original solution
from bisect import bisect_left


def eratosthenes(n):
    is_prime = [True] * (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


q = int(eval(input()))

p = eratosthenes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if p[i] and p[(i+1)//2]:
        l[i] = 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

res = []
for _ in range(q):
    l, r = list(map(int, input().split()))
    res.append(sum_l[r] - sum_l[l-1])

for v in res:
    print(v)

# Optimized solution
def eratosthenes(n):
    is_prime = [True] * (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


q = int(eval(input()))

p = eratosthenes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if p[i] and p[(i+1)//2]:
        l[i] = 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

res = []
for _ in range(q):
    l, r = list(map(int, input().split()))
    res.append(sum_l[r] - sum_l[l-1])

for v in res:
    print(v)
# Original solution
N = int(eval(input()))
l, r = [], []
for i in range(N):
  L,R=list(map(int,input().split()))
  l+= [L]
  r+= [R]
  
prime = [0,0]+[1]*10**5#素数テーブル
for i in range(10**3):#エラトステネスのふるいにかける
  if prime[i]==0: continue
  for j in range(i+1,10**5+1):
    if j%i==0: prime[j]=0
  
ans = []
for i in range(10**5+1):
  if prime[i]:
    if prime[(i+1)//2]: ans+=[1]
    else: ans+=[0]
  else: ans+=[0]
ans2= [0]
for i in range(10**5):
  ans2+=[ans2[-1]+ans[i+1]]
for i in range(N): 
  print((ans2[r[i]]-ans2[l[i]-1]))

# Optimized solution
N = int(eval(input()))

prime = [0,0]+[1]*10**5#素数テーブル
for i in range(10**3):#エラトステネスのふるいにかける
  if prime[i]==0: continue
  for j in range(2*i, 10**5+1, i):
    prime[j]=0
  
cumul = []
for i in range(10**5+1):
  if prime[i]:
    if prime[(i+1)//2]: cumul+=[1]
    else: cumul+=[0]
  else: cumul+=[0]
    
num_table = [0]
for i in range(10**5):
  num_table+=[num_table[-1]+cumul[i+1]]
  
for i in range(N):
  L,R=list(map(int,input().split()))
  print((num_table[R]-num_table[L-1]))
# Original solution
def isprime(x):
    for i in range(2 , int(x**0.5)+1):
        if x%i == 0:
            return False
    return True
N = 10**5
lst = []
for x in range(2,N):
    if isprime(x):
        lst.append(x)

q = int(eval(input()))
ans = []

for i in range(q):
    cnt = 0
    l,r = list(map(int,input().split()))
    for j in range(l,r+1,2):
        if j != 1 and j in lst and int((j+1)/2) in lst:
            cnt += 1
    ans.append(cnt)

for i in range(q):
    print((ans[i]))

# Optimized solution

import math
def eratosthenes(n):
    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]

_primes = eratosthenes(10**5)
primes = [False] * (10**5+1)

for p in _primes:
    primes[p] = True

like_2017 = [False] * (10**5+1)
for p in _primes:
    if primes[(p+1)//2]:
        like_2017[p] = True

c = 0
C = [0]
for i in range(1,10**5+1):
    if like_2017[i]:
        c += 1
    C.append(c)

q = int(eval(input()))
for _ in range(q):
    l,r = list(map(int,input().split()))
    print((C[r] - C[l-1]))
# Original solution
q = int(eval(input()))
ll = []
rr = []
for i in range(q):
    l,r = list(map(int,input().split()))
    ll.append(l)
    rr.append(r)

m = min(ll)
M = max(rr)
cnt = [0]*(M+2)

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

s = 0
for i in range(m,M+1,2):
    if is_prime(i) and is_prime((i+1)//2):
        s += 1
    cnt[i] = s

for i in range(q):
    print((cnt[rr[i]]-cnt[ll[i]-2]))

# Optimized solution
q = int(eval(input()))
ll = []
rr = []
for i in range(q):
    l,r = list(map(int,input().split()))
    ll.append(l)
    rr.append(r)

def f(n):
    flag = [True]*(n+1)
    flag[0] = flag[1] = False
    for i in range(2,int(n**0.5)+1):
        if flag[i]:
            x = 2*i
            while x <= n:
                flag[x] = False
                x += i
    return flag

m = max(rr)
j = f(m)
cnt = [0]*(m+1)
for i in range(1,m+1):
    cnt[i] = cnt[i-1]
    if i%2 != 0 and j[i] and j[(i+1)//2]:
        cnt[i] += 1

for i in range(q):
    print((cnt[rr[i]]-cnt[ll[i]-1]))
# Original solution
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

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

maximum = 100000
primes = sieve(maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if v and i >= l and i > 1 and i <= r and i % 2 == 1 and primes[(i + 1) // 2]:
            count += 1
    print(count)


# Optimized solution
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

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

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print((c[r]-c[l-1]))
# Original solution
dp = [1]*(10**5+1) #エラトステネスの篩
dp[0],dp[1] = 0, 0
for i in range(2, 10**5+1):
    if dp[i] == 0:
        continue
    j = i
    while j + i <= 10**5:
        j += i
        if dp[j] == 1:
            dp[j] = 0

ni = [0]*(10**5+1) #2012_like check
for i in range(2, 10**5+1):
    if dp[i] == 1 and dp[(i+1)//2] == 1:
        ni[i] = 1

ru = [0]*(10**5+1)
for i in range(1, 10**5+1):
    ru[i] = ru[i-1] + ni[i]

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

# Optimized solution
def f():    
    dp = [1]*(10**5+1) #エラトステネスの篩
    dp[0],dp[1] = 0, 0
    for i in range(2, 10**5+1):
        if dp[i] == 0:
            continue
        j = i
        while j + i <= 10**5:
            j += i
            if dp[j] == 1:
                dp[j] = 0
    
    ni = [0]*(10**5+1) #2012_like check
    for i in range(2, 10**5+1):
        if dp[i] == 1 and dp[(i+1)//2] == 1:
            ni[i] = 1
    
    ru = [0]*(10**5+1)
    for i in range(1, 10**5+1):
        ru[i] = ru[i-1] + ni[i]
    
    q = int(eval(input()))
    for i in range(q):
        l, r = list(map(int,input().split()))
        print((ru[r] - ru[l-1]))

if __name__ == '__main__':
    f()
# Original solution
primes = {2}
for i in range(1, 50000):
    i = 2 * i + 1
    for j in primes:
        if i % j == 0:
            break
    else:
        primes.add(i)

ret = set()
for i in primes:
    if (i + 1) // 2 in primes:
        ret.add(i)
ret = sorted(ret)


def binary(i):
    low = 0
    high = len(ret) - 1
    mid = 0
    while high - low > 1:
        mid = (high + low) // 2
        if ret[mid] < i:
            low = mid
        else:
            high = mid
    return low if ret[low] < i else -1


q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    low = binary(l)
    high = binary(r)
    high += 1 if ret[high+1] == r else 0
    print((high-low))


# Optimized solution
work = [True] * 100001
work[0] = False
work[1] = False
primes = []
for i in range(100001):
    if work[i]:
        for j in range(2* i, 100001, i):
            work[j] = False


csum = [0] * 100001
index = 0
for i in range(1, 100001):
    if work[i] and work[(i+1)//2]:
        csum[i] = csum[i - 1] + 1
    else:
        csum[i] = csum[i - 1]

q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    low = csum[l-1]
    high = csum[r]
    print((high-low))
# Original solution
def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime
from bisect import bisect_left as bl
lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(eval(input()))
lis = set(lis)-{0}
lis = sorted(tuple(lis))
for _ in range(Q):
    l,r = list(map(int,input().split()))
    t = bl(lis,l)
    tmp = 0
    if t == len(lis):print(tmp);continue
    while t < len(lis) and lis[t] <= r:
        tmp += 1
        t += 1
    print(tmp)



# Optimized solution
def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime
from bisect import bisect_left as bl
from bisect import bisect_right as br
lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(eval(input()))
lis = set(lis)-{0}
lis = sorted(tuple(lis))
for _ in range(Q):
    l,r = list(map(int,input().split()))
    t = bl(lis,l)
    s = br(lis,r)
    tmp = s-t
    print(tmp)
# Original solution
def make_divisors(n):  
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
def islike2017(i):
  if i%2==0:
    return False
  if len(make_divisors(i))==2:
    if len(make_divisors(((i+1)//2)))==2:
      return True
  return False
def main():
  q=int(eval(input()))
  lr=[list(map(int,input().split())) for _ in range(q)]
  all=[lri[0] for lri in lr]
  all[q:q]=[lri[1] for lri in lr]
  all.sort()
  d={}
  c=0
  d[all[0]]=c
  for i in range(2*q-1):
    for j in range(all[i],all[i+1]):
      if islike2017(j):
        c+=1
    d[all[i+1]]=c
  for l,r in lr:
    a=d[r]-d[l]
    a+=1 if islike2017(r) else 0
    print(a)
  
if __name__=='__main__':
  main()


# Optimized solution
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
def main():
  q=int(eval(input()))
  lr=[list(map(int,input().split())) for _ in range(q)]
  all=[lri[0] for lri in lr]
  all[q:q]=[lri[1] for lri in lr]
  all.sort()
  d={}
  c=0
  d[all[0]]=c
  for i in range(2*q-1):
    for j in range(all[i],all[i+1]):
      if is_prime(j) and is_prime((j+1)//2):
        c+=1
    d[all[i+1]]=c
  for l,r in lr:
    a=d[r]-d[l]
    a+=1 if is_prime(r) and is_prime((r+1)//2) else 0
    print(a)
  
if __name__=='__main__':
  main()
# Original solution
def is_prime(n):
    for i in range(2, int(n**(1/2))+1, 1):
        if n%i == 0:
            return False
    return n != 1

def lnum(n):  # Like number
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False

MAX = 101010
a = [0]*MAX
for i in range(MAX):
    if lnum(i):
        a[i] = 1
    else:
        continue

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

# Optimized solution
def is_prime(n):
    for i in range(2, int(n**(1/2))+1, 1):
        if n%i == 0:
            return False
    return n != 1

def lnum(n):  # Like number
    if is_prime(n) and is_prime((n+1)//2):
        return True
    else:
        return False

MAX = 10**5+10
a = [0]*MAX
for i in range(MAX):
    if lnum(i):
        a[i] = 1
    else:
        continue

s = [0]*MAX
for i in range(MAX-1):
    s[i+1] = s[i] + a[i]
    
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((s[r+1]-s[l]))
# Original solution
import math
primes = [True]*(10**5+1)
primes[0],primes[1] = False,False
cumsum = [0]*(10**5+1)

for i in range(2, int(math.sqrt(10**5)+1)):
  if primes[i]:
    j = 2
    while i*j <= 10**5:
      primes[i*j] = False
      j += 1

for i in range(2, 10**5+1):
  if primes[i] and primes[(i+1)//2]:
    cumsum[i] = cumsum[i-1]+1
  else:
    cumsum[i] = cumsum[i-1]

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

# Optimized solution
MAX_INT = 10**5+1
primes = [True] * (10**5+1)
primes[0], primes[1] = False, False
for i in range(2, int(MAX_INT**0.5)+1):
  if primes[i]:
    for j in range(i*2, MAX_INT, i):
      primes[j] = False

cumsum = [0] * (10**5+1)
for i in range(1, 10**5+1, 2):
  if primes[i] and primes[(i+1)//2]:
      cumsum[i] = 1

for i in range(1, 10**5+1):
  cumsum[i] += cumsum[i-1]

Q = int(eval(input()))
for _ in range(Q):
  l,r = list(map(int,input().split()))
  print((cumsum[r]-cumsum[l-1]))
# Original solution
q = int(eval(input()))

num = [i for i in range(2,10**5+1)]
so = []
while len(num):
  i = num[0]
  so.append(i)
  num = [j for j in num if j%i!=0]

import bisect

like2017 = []
for sos in so:
  l_idx = bisect.bisect_left(so, (sos+1)//2)
  if l_idx>=len(so) or sos%2==0:continue
  if so[l_idx]==(sos+1)//2:
    like2017.append(sos)
#print(like2017[:20])  

for _ in range(q):
  ans = 0
  l, r = list(map(int, input().split()))
  l_idx = bisect.bisect_left(like2017, l)
  r_idx = bisect.bisect_right(like2017, r)
  #print(l_idx, r_idx)
  ans = r_idx-l_idx
  print(ans)

# Optimized solution
q = int(eval(input()))
n = 10**5+1
p = [0]*n
p[2] = 1
for i in range(3,10**5+1):
  prime = 1
  for j in range(2, int(i**0.5)+1):
    if i%j==0:
      prime = 0
      break
  if prime:
    p[i] = 1

like2017 = [1 if p[i] and p[(i+1)//2] else 0 for i in range(n)]
cnter = [0]*n
for i in range(1,n):
  cnter[i] = cnter[i-1]+ like2017[i]

for _ in range(q):
  ans = 0
  l, r = list(map(int, input().split()))
  ans = cnter[r]-cnter[l-1]
  print(ans)
# Original solution
from bisect import bisect_left, bisect_right
import random
def is_prime(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
 
    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

prime = []
like = [3]
for i in range(3, 10**5+1):
    if is_prime(i):
        prime.append(i)
p_set = set(prime)
for i in prime:
    if (i+1)//2 in p_set:
        like.append(i)

Q = int(eval(input()))

for _ in range(Q):
    l, r = list(map(int,input().split()))
    print((bisect_right(like, r) - bisect_left(like, l)))

# Optimized solution
from bisect import bisect_left, bisect_right
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(3,n + 1) if is_prime[i]]

prime = primes(10**5)
p_set = set(prime)
like = [3]
for i in prime:
    if (i+1)//2 in p_set:
        like.append(i)

Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int,input().split()))
    print((bisect_right(like, r) - bisect_left(like, l)))
# Original solution
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return list(map(int, sys.stdin.readline().split()))
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

Q = ii()
lr = li2(Q)
from collections import deque
que = deque()

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

prime = [0]*(10**5+1)
flag = [0]*(10**5+1)
prime[2] = 1

for i in range(3, 10**5+1, 2):
    if is_prime(i):
        prime[i] = 1

for i in range(3, 10**5+1, 2):
    if prime[i] and prime[(i+1)//2]:
        flag[i] = 1

ans = list(accumulate(flag))

for i in range(Q):
    print((ans[lr[i][1]]-ans[lr[i][0]-1]))

# Optimized solution
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return list(map(int, sys.stdin.readline().split()))
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from itertools import accumulate #list(accumulate(A))

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

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    #table = [ i for i in range(1, n+1) if is_prime[i-1]]
    #return is_prime, table
    return is_prime
'''

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

    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    #table = [ i for i in range(1, n+1) if is_prime[i-1]]
    #return is_prime, table
    return is_prime


Q = ii()
lr = li2(Q)

prime = sieve(10**5)
flag = [0]*(10**5+1)

for i in range(3, 10**5+1, 2):
    if prime[i] and prime[(i+1)//2]:
        flag[i] = 1

ans = list(accumulate(flag))

for i in range(Q):
    print((ans[lr[i][1]] - ans[lr[i][0]-1]))
# Original solution
import bisect
a = [True] * 100001
a[0] = False
a[1] = False
p = []
for i in range(2, 100001):
    if a[i]:
        for j in range(i * 2, 100001, i):
            if a[j]:
                a[j] = False
        if i % 2 != 0 and a[(i + 1) // 2]:
            p.append(i)
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((bisect.bisect_right(p, r) - bisect.bisect_left(p, l)))


# Optimized solution
def slove():
    import sys
    input = sys.stdin.readline
    pl = {}
    p = [True] * (10 ** 5 + 1)
    p[0] = False
    p[1] = False
    cnt = 0
    pll = [0] * (10 ** 5 + 1)
    for i in range(2, len(p)):
        if p[i]:
            pl[i] = 1
            for j in range(i, len(p), i):
                p[j] = False
        if i % 2 != 0:
            if (i + 1) // 2 in pl and i in pl:
                cnt += 1
        pll[i] = cnt
    q = int(input().rstrip('\n'))
    lr = [list(map(int, input().rstrip('\n').split())) for _ in range(q)]
    for l, r in lr:
        print((pll[r] - pll[l-1]))


if __name__ == '__main__':
    slove()
# Original solution
def slove():
    import sys
    input = sys.stdin.readline
    pl = {}
    p = [True] * (10 ** 5 + 1)
    p[0] = False
    p[1] = False
    cnt = 0
    pll = [0] * (10 ** 5 + 1)
    for i in range(2, len(p)):
        if p[i]:
            pl[i] = 1
            for j in range(i, len(p), i):
                p[j] = False
        if i % 2 != 0:
            if (i + 1) // 2 in pl and i in pl:
                cnt += 1
        pll[i] = cnt
    q = int(input().rstrip('\n'))
    lr = [list(map(int, input().rstrip('\n').split())) for _ in range(q)]
    for l, r in lr:
        print((pll[r] - pll[l-1]))


if __name__ == '__main__':
    slove()


# Optimized solution
def slove():
    import sys
    input = sys.stdin.readline
    pb = [True] * (10 ** 5 + 1)
    pb[0] = False
    pb[1] = False
    pl = [0] * (10 ** 5 + 1)
    pc = 0
    for i in range(2, len(pb)):
        if pb[i]:
            for j in range(i + i, len(pb), i):
                if pb[j]:
                    pb[j] = False
            if pb[(i + 1) // 2]:
                pc += 1
        pl[i] = pc
    n = int(input().rstrip('\n'))
    for i in range(n):
        l, r = list(map(int, input().rstrip('\n').split()))
        print((pl[r] - pl[l-1]))


if __name__ == '__main__':
    slove()
# Original solution
import bisect
q = int(eval(input()))
l = []
r = []
for _ in range(q):
    line = list(map(int, input().split()))
    l.append(line[0])
    r.append(line[1])
like2017 = []
pn = [2]
for L in range(3, 10**5):
    chk = True
    for L2 in pn:
        if L%L2 == 0:
            chk = False
            break
    if chk:
        pn.append(L)
for prime in pn:
    if (prime+1)//2 in pn:
        like2017.append(prime)
for i in range(q):
    left = bisect.bisect_left(like2017, l[i])
    right = bisect.bisect_right(like2017,r[i])
    print((right - left))

# Optimized solution
import bisect
q = int(eval(input()))
l = []
r = []
for _ in range(q):
    line = list(map(int, input().split()))
    l.append(line[0])
    r.append(line[1])
like2017 = []
pn = [2]
for L in range(3, 10**5):
    chk = True
    for L2 in pn:
        if L%L2 == 0:
            chk = False
            break
    if chk:
        pn.append(L)
def bisect_in(x, line):
    return line[bisect.bisect_left(line, x)] == x
for prime in pn:
    if bisect_in((prime+1)//2, pn):
        like2017.append(prime)
for i in range(q):
    left = bisect.bisect_left(like2017, l[i])
    right = bisect.bisect_right(like2017,r[i])
    print((right - left))