CodeEff/ECCO huggingface dataset:
# Original solution
f=[True]*(10**5+1)
like=[False]*(10**5+1)
f[0]=False
f[1]=False
import math
for i in range(2,len(f)):
  fact=True
  for j in range(2,int(math.sqrt(i))+1):
    if i%j==0:
      fact=False
      break
  
  if fact:
    f[i]=True
    if i*2-1<len(like):
      like[i*2-1]=True
    for p in range(i*2,len(f),i):
      f[p]=False

sums=[0]*(10**5+1)
cur=0
for i in range(len(sums)):
  if f[i] and like[i]:
    sums[i]=cur+1
    cur+=1
  else:
    sums[i]=cur

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


# Optimized solution
f=[True]*(10**5+1)
like=[False]*(10**5+1)
f[0]=False
f[1]=False
import math
for i in range(2,len(f)):
  if not f[i]:
    continue
  fact=True
  for j in range(2,int(math.sqrt(i))+1):
    if i%j==0:
      fact=False
      break
  
  if fact:
    f[i]=True
    if i*2-1<len(like):
      like[i*2-1]=True
    for p in range(i*2,len(f),i):
      f[p]=False

sums=[0]*(10**5+1)
cur=0
for i in range(len(sums)):
  if f[i] and like[i]:
    sums[i]=cur+1
    cur+=1
  else:
    sums[i]=cur

Q=int(eval(input()))
for i in range(Q):
  l,r=list(map(int,input().split()))
  print((sums[r]-sums[l-1]))
# Original solution
f=[True]*(10**5+1)
like=[False]*(10**5+1)
f[0]=False
f[1]=False
import math
for i in range(2,len(f)):
  if not f[i]:
    continue
  fact=True
  for j in range(2,int(math.sqrt(i))+1):
    if i%j==0:
      fact=False
      break
  
  if fact:
    f[i]=True
    if i*2-1<len(like):
      like[i*2-1]=True
    for p in range(i*2,len(f),i):
      f[p]=False

sums=[0]*(10**5+1)
cur=0
for i in range(len(sums)):
  if f[i] and like[i]:
    sums[i]=cur+1
    cur+=1
  else:
    sums[i]=cur

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


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

fact=[True]*(10**5+1)
fact[0]=False
fact[1]=False

num=[0]*(10**5+1)
cur=0
for i in range(len(fact)):
  if fact[i]:
    for j in range(i*2,len(fact),i):
      fact[j]=False
    if fact[(i+1)//2]:
      cur+=1
  num[i]=cur
      
for i in range(Q):
  l,r=list(map(int,input().split()))
  print((num[r]-num[l-1]))
# Original solution
p,q,r = [2],[],[]
k = 3
while k < 100000:
  flag = True
  for t in p:
    if t*t > k:
      break
    if k%t == 0:
      flag = False
  if flag:
    p.append(k)
  k += 2
for t in p[1:]:
  if (t+1)//2 in p:
    q.append(t)
q.append(100000+3)
k = 0
for i in range(99999//2+1):
  while q[k]<=2*i+1:
    k += 1
  r.append(k)
c = int(eval(input()))
while c>0:
  x,y = list(map(int,input().split()))
  print((r[y//2]-r[max(x,3)//2-1]))
  c -= 1
  

# Optimized solution
N = 10**5
p = [0]*(N+1)
q = [0]*(N+1)

p[2] = 1
primes = [2]

for i in range(3,N+1):
  f = 1
  for t in primes:
    if t*t > i:
      break
    if i%t == 0:
      f = 0
      break
  if f == 1:
    primes.append(i)
    p[i] = 1
    if p[(i+1)//2]:
      q[i] = 1
m = 0
s = [0]*(N+1)
for i in range(1,N+1):
  m += q[i]
  s[i] = m
  
for i in range(int(eval(input()))):
  l,r = list(map(int,input().split()))
  print((s[r]-s[l-1]))
# Original solution
# https://atcoder.jp/contests/abc084/tasks/abc084_d
from bisect import bisect_left, bisect_right
q = int(eval(input()))
queries = []
MAX = 0
for _ in range(q):
    l, r = list(map(int, input().split()))
    queries.append((l, r))
    MAX = max([MAX, l, r])

def is_prime(x):
    sqrt = x ** 0.5
    i = 2
    while i <= sqrt:
        if x % i == 0:
            return False
        i += 1
    return True

def eratos(x):
    dp = [True] * (x + 1)
    dp[0] = dp[1] = False
    i = 2
    sqrt = x ** 2
    while i <= sqrt:
        for j in range(i * 2, x + 1, i):
            dp[j] = False
        i += 1
    primes = []
    for i in range(len(dp)):
        if dp[i]:
            primes.append(i)
    return primes, dp
primes, dp = eratos(MAX)
sub_prims = []
for p in primes:
    x = (p + 1) // 2
    if dp[x]:
        sub_prims.append(p)

for l, r in queries:
    left = bisect_left(sub_prims, l)
    right = bisect_left(sub_prims, r + 1)
    print((right - left))

# Optimized solution
# https://atcoder.jp/contests/abc084/tasks/abc084_d
from bisect import bisect_left, bisect_right
q = int(eval(input()))
queries = []
MAX = 0
for _ in range(q):
    l, r = list(map(int, input().split()))
    queries.append((l, r))
    MAX = max([MAX, l, r])
from datetime import datetime
s = datetime.now()
def eratos(x):
    dp = [True] * (x + 1)
    dp[0] = dp[1] = False
    i = 2
    sqrt = x ** 0.5
    while i <= sqrt:
        if dp[i]:
            for j in range(i ** 2, x + 1, i):
                dp[j] = False
        i += 1
    primes = []
    for i in range(len(dp)):
        if dp[i]:
            primes.append(i)
    return primes, dp

primes, dp = eratos(MAX)
sub_prims = []
for p in primes:
    x = (p + 1) // 2
    if dp[x]:
        sub_prims.append(p)

for l, r in queries:
    left = bisect_left(sub_prims, l)
    right = bisect_left(sub_prims, r + 1)
    print((right - left))
# Original solution
import math


def get_sieve_of_eratosthenes(n):# エラトステネスのふるい(O(NloglogN)). ~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]


Q = int(input())
ls = [0]
prime = set(get_sieve_of_eratosthenes(10**5 + 10))

output = []
for i in range(1, 10**5+1):
    if (i in prime) & (int((i+1)/2) in prime):
        ls.append(ls[i-1]+1)
    else: ls.append(ls[i-1])
#print(ls[:10])
for q in range(Q):
    l, r = map(int, input().split())
    output.append(ls[r]-ls[l-1])
print(*output, sep="\n")



# Optimized solution
import math


def get_sieve_of_eratosthenes(n):# エラトステネスのふるい(O(NloglogN)). ~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]


Q = int(input())
ls = [0]
prime = set(get_sieve_of_eratosthenes(10**5 + 10))

output = []
for i in range(10**5+10):
    if (i in prime) & (int((i+1)/2) in prime):
        ls.append(ls[-1]+1)
    else: 
        ls.append(ls[-1])

for q in range(Q):
    l, r = map(int, input().split())
    output.append(ls[r+1]-ls[l])
print(*output, sep="\n")
# Original solution
import math
import bisect
Q=int(eval(input()))

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

def siever(x):
  nums = [a for a in range(2,x+1)]
  primes = []
  while nums[0] <= int(math.sqrt(x))+1:
    tmp = nums.pop(0)
    primes.append(tmp)
    for num in nums:
      if num%tmp == 0:
        nums.remove(num)
        continue
  
  return (primes+nums)

L = 0
for query in querys:
  L = max(L,query[1])
primes = siever(L)
L2017= []
for prime in primes:
  if (prime+1)//2 in primes:
    L2017.append(prime)
result = [0]*(max(L2017)+1)
for l in L2017:
  result[l] = 1
for i in range(1,len(result)):
  result[i] += result[i-1]
for query in querys:
  if query[0] == query[1] and query[0] in L2017:
    print((1))
  else:
    if len(result) <= query[0]:
      print((0))
    elif len(result) <= query[1]:
      print((result[-1]-result[query[0]-1]))
    else:
      print((result[query[1]]-result[query[0]-1]))

# Optimized solution
import math
Q=int(eval(input()))
querys = [list(map(int,input().split())) for x in range(Q)]
large = max(q[1] for q in querys)
like2017 = [0]*(large+1)

#siever
cands = [False if (5 < i and (i%2)*(i%3)*(i%5) == 0) or (i < 2) or (i == 4) else True for i in range(large+1)]
if 5 <= large:
  for i in range(6,int(math.sqrt(large)+1)):
    if cands[i]:
      for j in range(i*i,large+1,i):
        if cands[j]:
          cands[j] = False

#find 2017-like-number          
for x in range(large+1):
  if cands[x] and cands[(x+1)//2]:
    like2017[x] = 1
for y in range(1,large+1):
  like2017[y] += like2017[y-1]

for q in querys:
  print((like2017[q[1]]-like2017[q[0]-1]))
# Original solution
def solve():
    q = int(eval(input()))
    l, r = [], []
    for _ in range(q):
        tmp_l, tmp_r = list(map(int, input().split(" ")))
        l.append(tmp_l)
        r.append(tmp_r)

    p = [True for i in range(100000)]
    p[0] = p[1] = False
    for i in range(2, 100000):
        if p[i]:
            for j in range(2 * i, 100000, i):
                p[j] = False

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

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

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


solve()

# Optimized solution
def prime_TorF(n):
    p = [True for i in range(n)]
    p[0] = p[1] = False
    for i in range(2, 100000):
        if p[i]:
            for j in range(2 * i, 100000, i):
                p[j] = False

    return p


def solve():
    q = int(eval(input()))
    l, r = [], []
    for _ in range(q):
        tmp_l, tmp_r = list(map(int, input().split(" ")))
        l.append(tmp_l)
        r.append(tmp_r)

    p = prime_TorF(100000)

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

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

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


solve()
# Original solution
import math
q=int(eval(input()))
lr=[list(map(int, input().split())) for i in range(q)]

l,r=[],[]
for a in lr:
    l.append(a[0])
    r.append(a[1])

ss = [i for i in range(1,max(r)+1)]
for i in range(2,int(math.sqrt(max(r)))+1):
    for j in range(2*i,max(r)+1,i):
        ss[j-1]=0
for j in range(q):
    ans=0
    for i in range(l[j],r[j]+1,2):
        if i in ss and (i+1)//2 in ss:
            ans+=1
    if l[j]==1:
        ans-=1
    print(ans)

# Optimized solution
q=int(eval(input()))
lr=[list(map(int, input().split())) for i in range(q)]
l,r=[],[]
for a in lr:
    l.append(a[0])
    r.append(a[1])
mr=max(r)
x = [True]*(mr+1)
x[0]=False
x[1]=False

for i in range(mr+1):
    if x[i]:
        for j in range(2*i, mr+1, i):
            x[j] = False
c=[0]*(mr+1)
for i in range(1,mr+1):
    if x[i] and x[(i+1)//2]:
        c[i] = c[i-1]+1
    else:
        c[i] = c[i-1]
for i in range(q):
    print((c[r[i]]-c[l[i]-1]))
# Original solution
import bisect

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

N=[3]
for i in range(5,100001,2):
    if PN(i) and PN((i+1)//2):
        N.append(i)

Q=int(eval(input()))

for i in range(Q):
    l,r=list(map(int,input().split()))
    ln1=bisect.bisect_left(N,l)
    ln2=bisect.bisect_right(N,l)
    rn1=bisect.bisect_left(N,r)
    rn2=bisect.bisect_right(N,r)
    if ln1==ln2 and rn1==rn2:
        print((rn1-ln1))
    elif ln1==ln2 or rn1==rn2:
        print((rn1-ln2+1))
    else:
        print((rn1-ln2+2))





# Optimized solution
def PrimeNumber(N):
    f=[1]*(N+1)
    f[0]=0
    f[1]=0

    for i in range(2,N+1):
        if f[i]==0:
            continue
        j = 2
        temp = i
        while temp * j <= N:
            f[temp*j]=0
            j += 1

    return f

PN=PrimeNumber(100000)
C=[0]*100001

C[1]=0

for i in range(2,100001):
    if PN[i]==1 and PN[(i+1)//2]==1:
        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
# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(eval(input()))
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = list(map(int, input().split(" ")))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0:
			continue
		if (i+1) % 2 == 0 and is_prime3(i) == True:
			tmp = (i+1) / 2
			tmp = int(tmp)
			if is_prime3(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		#print(base)
		print((base[r] - base[l-1]))
			
				
		
def getPrimeNumList(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_prime3(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
	
if __name__ == "__main__":
	main()


# Optimized solution
# -*- coding: utf-8 -*-
import sys
import random

def main():
	Q = int(eval(input()))
	maps = []
	r_max = 0
	for _ in range(Q):
		l, r = list(map(int, input().split(" ")))
		maps.append((l, r))
		if r_max < r:
			r_max = r
			
	#marix = getPrimeNumList(r_max)
				
	base = [0] * (r_max+1)
	counts = 0
	for i in range(r_max+1):
		if i == 0 or i == 1:
			continue
		if (i+1) % 2 == 0 and is_prime(i) == True:
			tmp = (i+1) / 2
			if is_prime(tmp) == True:
				counts += 1
		base[i] = counts
			
	
	for i in maps:
		l, r = i
		print((base[r] - base[l-1]))
			
		
def getPrimeNumList(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_prime(n): 
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True
	
if __name__ == "__main__":
	main()
# Original solution
def d_2017LikeNumber(Q, I):  # Q:クエリの数、I:探索区間の左端と右端
    def prime_list(M):
        # 0以上M以下の素数のリスト
        s = [True] * (M + 1)  # i番目の要素はiが素数ならTrue、非素数ならFalse
        s[0] = s[1] = False
        for x in range(2, int(M**0.5) + 1):
            if s[x]:
                for i in range(x + x, len(s), x):
                    # 素数xの倍数は素数ではない
                    s[i] = False
        return s

    def calc_like2017(M, p):
        # i番目の要素が、1以上i以下の"2017に似た数"の個数となるようなリスト
        # 0番目は0と定義する
        # M以下の素数のリストpを予め作っておく必要がある
        c = [0] * (M + 1)
        for i in range(3, M + 1, 2):  # 0,1,2は定義上2017に似た数にならない
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, M + 1):
            c[i] += c[i - 1]
        return c

    c = calc_like2017(10**5, prime_list(10**5))
    ans = ''
    for query in I:
        l, r = query[0], query[1]
        ans += '{}\n'.format(c[r] - c[l - 1])
    return ans[:-1]

Q = int(eval(input()))
I = [[int(i) for i in input().split()] for j in range(Q)]
print((d_2017LikeNumber(Q, I)))

# Optimized solution
def d_2017_like_number():
    Q = int(eval(input()))
    I = [[int(i) for i in input().split()] for j in range(Q)]

    def prime_table(n):
        """n 以下の整数がそれぞれ素数かどうかのリスト (エラトステネスの篩)"""
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False  # 0と1は素数でない
        for j in range(2, int(n**0.5) + 1):
            if not is_prime[j]:
                continue
            for k in range(j * 2, n + 1, j):
                is_prime[k] = False  # jの倍数は素数でない
        return is_prime

    def calc_like2017(m, p):
        # i 番目の要素が、1 以上 i 以下の "2017に似た数" の個数となるリストを返す
        # m 以下の素数のリスト p を予め作っておく必要がある
        c = [0] * (m + 1)  # 0番目は0と定義する
        for i in range(3, m + 1, 2):  # 0, 1, 2 は定義上2017に似た数にならない
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, m + 1):
            c[i] += c[i - 1]
        return c

    like2017 = calc_like2017(10**5, prime_table(10**5))
    ans = [like2017[r] - like2017[l - 1] for l, r in I]
    return '\n'.join(map(str, ans))

print((d_2017_like_number()))
# Original solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))
P = [n for n in P if (n + 1) // 2 in P]
a = [0] * (N + 1)
for n in P:
    a[n] = 1
a = list(accumulate(a))

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


# Optimized solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))
P = [n for n in P if (n + 1) // 2 in P]
a = [0] * (N + 1)
for n in P:
    a[n] = 1
a = list(accumulate(a))

Q, *LR = list(map(int, open(0).read().split()))
for l, r in zip(*[iter(LR)] * 2):
    print((a[r] - a[l - 1]))
# Original solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

Q, *LR = list(map(int, open(0).read().split()))
for l, r in zip(*[iter(LR)] * 2):
    print((a[r] - a[l - 1]))


# Optimized solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

ans = []
Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

print(*ans, sep='\n')
# Original solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

ans = []
Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

print(*ans, sep='\n')


# Optimized solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

ans = []
Q, *LR = list(map(int, open(0).read().split()))
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

print(('\n'.join(map(str, ans))))
# Original solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = tuple(accumulate(a))

ans = []
Q, *LR = list(map(int, open(0).read().split()))
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

print(('\n'.join(map(str, ans))))


# Optimized solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}

def main():
    N = 10 ** 5
    primes = prime_numbers(N)
    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
    a = tuple(accumulate(a))

    ans = []
    Q, *LR = list(map(int, open(0).read().split()))
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(a[r] - a[l - 1])

    print(('\n'.join(map(str, ans))))

if __name__ == "__main__":
    main()