CodeEff/ECCO huggingface dataset:
# Original 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]))

# Optimized solution
from itertools import accumulate


# エラトステネスの篩
# is_prime := 1~nが素数か否か
# table := 2~nのうち素数
def sieve(n):
    is_prime = [True for _ in range(n)]
    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


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

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

max_R = max(R)
is_prime, table = sieve(max_R)

check = [0]*(max_R + 1)
for i in range(0, max_R + 1):
    if (i % 2 == 1):
        if (is_prime[i-1] and is_prime[(i+1)//2-1]):
            check[i] = 1

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

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

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

max_lr = 100000
er_list = eratosthenes(max_lr)
count = [0] * max_lr


for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1
            
count = list(accumulate(count))
            
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((count[r]-count[l-1]))

# Optimized solution
import math
from itertools import accumulate

def eratosthenes(n):
    is_prime = [True for _ in range(n)]
    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 table

max_lr = 100000
er_list = eratosthenes(max_lr)
count = [0] * max_lr


for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1
            
count = list(accumulate(count))
            
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((count[r]-count[l-1]))
# Original solution
from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n):
    """
    nが素数かどうか判定する
    """
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        i = 3
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 2
        return True


size = 10 ** 5 + 1
memo = [0] * size
for n in range(3, size):
    memo[n] = memo[n - 1]
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        memo[n] += 1

Q = int(eval(input()))
for _ in range(Q):
    left, right = list(map(int, input().split(' ')))
    print((memo[right] - memo[left - 1]))


# Optimized solution
size = 10 ** 5 + 1
is_primes = [True] * size
is_primes[0] = False
is_primes[1] = False
for n in range(2, size):
    if not is_primes[n]:
        continue

    m = n * 2
    while m < size:
        is_primes[m] = False
        m += n

dp = [0] * size
for i in range(1, size):
    dp[i] = dp[i - 1]
    if i % 2 == 1 and is_primes[i] and is_primes[(i + 1) // 2]:
        dp[i] += 1

Q = int(eval(input()))
for _ in range(Q):
    left, right = list(map(int, input().split(' ')))
    print((dp[right] - dp[left - 1]))
# Original solution
import math
Primes = {2}
Sim = [0 for i in range(100002)]

for i in range(3, 100001):
    if i % 2 == 0:
        Sim[i] = Sim[i-1]
    else:
        for p in Primes:
            if i % p == 0:
                Sim[i] = Sim[i-1]
                break
        else:
            Primes |= {i}
            if (i+1)//2 in Primes:
                Sim[i] = Sim[i-1] + 1
            else:
                Sim[i] = Sim[i-1]

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

# Optimized solution
Num = [int(i) for i in range(2, 100001)]
Primes = [True for i in range(100001)]
Sim = [0 for i in range(100001)]

for i in range(2, 100001):
    if Primes[i] == True:
        j = i * 2
        while j < 100001:
            Primes[j] = False
            j += i

for i in range(3, 100001):
    if Primes[i] and Primes[(i+1)//2]:
        Sim[i] = Sim[i-1] + 1
    else:
        Sim[i] = Sim[i-1]

Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((Sim[r] - Sim[l-1]))
# Original solution
Num = [int(i) for i in range(2, 100001)]
Primes = [True for i in range(100001)]
Sim = [0 for i in range(100001)]

for i in range(2, 100001):
    if Primes[i] == True:
        j = i * 2
        while j < 100001:
            Primes[j] = False
            j += i

for i in range(3, 100001):
    if Primes[i] and Primes[(i+1)//2]:
        Sim[i] = Sim[i-1] + 1
    else:
        Sim[i] = Sim[i-1]

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

# Optimized solution
import sys

def solve():
    input = sys.stdin.readline
    isPrime = [True] * (1 + 10**5)
    isPrime[0] = isPrime[1] = False
    Like = [0] * (1 + 10 ** 5)

    for i in range(2, 1 + 10 ** 5):
        if isPrime[i]:
            k = 2 * i
            while k <= 10 ** 5:
                isPrime[k] = False
                k += i
            if i % 2 == 1 and isPrime[(i + 1) // 2]: Like[i] = Like[i-1] + 1
            else: Like[i] = Like[i-1]
        else: Like[i] = Like[i-1]
                
    Q = int(eval(input()))
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        print((Like[r] - Like[l-1]))

    return 0

if __name__ == "__main__":
    solve()
# Original solution
import math

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

MAX=10**5
limit=int(math.sqrt(MAX))
primes=[2]
table=[i+1 for i in range(2,MAX,2)]
while limit>table[0]:
  primes.append(table[0])
  table=[j for j in table if j%table[0] != 0]
table=primes+table

similars=[]
for i in range(len(table)):
  n=table[i]
  if (n+1)//2 in table:
    similars.append(n)

for i in lr:
  l=i[0]
  r=i[1]
  cand=[x for x in similars if l<=x<=r]
  print((len(cand)))

# Optimized solution
import math
from itertools import accumulate

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

MAX=10**5
limit=int(math.sqrt(MAX))
primes=[2]
table=[i+1 for i in range(2,MAX,2)]
while limit>table[0]:
  primes.append(table[0])
  table=[j for j in table if j%table[0] != 0]
primes=set(primes+table)

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

similars=list(accumulate(similars))

for i in lr:
  l=i[0]
  r=i[1]
  print((similars[r]-similars[l-1]))
# Original solution
import sys

def f(d):
    num = 3
    p = [2]
    c = 0
    while num <= 10**5:
        m = int(num**0.5)
        while m > 1 and num % m != 0:
            m -= 1
        if m == 1:
            p.append(num)
            if (num+1)//2 in p:
                c += 1
        d[num] = c
        num += 2
    return d


def main():
    input = sys.stdin.readline
    Q = int(eval(input()))
    d = {1: 0, 2: 0}
    d = f(d)
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        l = max(l - 2, 1)
        print((d[r] - d[l]))


if __name__ == '__main__':
    main()


# 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

MAX = 10**5+1

is_prime = [True] * (MAX+1)
is_prime[0] = False
is_prime[1] = False

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

likes = [0] * (MAX+1)
for i in range(0, MAX+1):
    if i % 2 == 0: continue
    if is_prime[i] and is_prime[(i+1)//2]:
        likes[i] = 1
    
c = [0] * (MAX+1)
for i in range(MAX):
    c[i+1] = c[i] + likes[i]

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

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







# Optimized solution
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(eval(input())) #整数読み込み
def ifn(): return float(eval(input())) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return list(map(int, input().split())) #整数map取得
def fmn(): return list(map(float, input().split())) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

def is_prime(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 is_prime

Q = iin()
lr = [iln() for _ in range(Q)]
max_v = 10**5
prime = is_prime(max_v)

c = [0 for _ in range(max_v+1)]
for i in range(max_v):
    c[i+1] = c[i]
    if i % 2 == 1 and prime[i] and prime[((i+1)//2)]: 
        c[i+1] += 1
for i in range(Q):
    l = lr[i][0]
    r = lr[i][1]
    print((c[r+1] - c[l]))
# Original solution
import bisect
N = 10**5
Q = int(eval(input()))

lst1 = [2]
for L in range(3, N, 2):
    if all(L % L2 != 0 for L2 in lst1):
        lst1.append(L)

lst1 = set(lst1) 
lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

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

# Optimized solution
import bisect, math
N = 10**5
Q = int(eval(input()))

lst1 = [2]
for L in range(3, N, 2):
  f = 0
  for d in range(3, math.floor(math.sqrt(L))+1, 2):
    if L % d == 0:
      f = 1
      break
  if f == 0:
    lst1.append(L)

lst1 = set(lst1) 
lst2 = [i for i in lst1 if (i+1)//2 in lst1]

lst2.sort()

for _ in range(Q):
  l, r = list(map(int, input().split()))
  a = bisect.bisect_left(lst2, l)
  b = bisect.bisect_right(lst2, r)
  print((b-a))
# Original solution
def prime_list(n):
	primes = set(range(2, n + 1))
	for i in range(2, int(n ** 0.5 + 1)):
		primes.difference_update(list(range(i * 2, n + 1, i)))
	return list(primes)

q = int(eval(input()))
primes = prime_list(10**5)

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



# Optimized solution
# O(nloglogn) https://mathtrain.jp/eratosthenes
def sieve(n):
	s = [True] * n
	s[0] = s[1] = False
	for x in range(2, int(n ** 0.5) + 1):
		if s[x]:
			for i in range(2 * x, n, x):
				s[i] = False
	return s

is_prime = sieve(10 ** 5 + 1)
is_like2017 = [False] * (10 ** 5 + 1)
for i in range(10**5 + 1):
	if is_prime[i] and is_prime[(i + 1) // 2]:
		is_like2017[i] = True

# 区間内のlike2017を求める
# 累積和を用いて高速化
c = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	if is_like2017[i]:
		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
import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    #prime_list = []
    like2017_list = []
    for prime in range(3,num+1,2):
#        if isPrime[prime]:
#            prime_list.append(prime)
        if isPrime[int(prime)] and isPrime[int((prime+1)/2)]:
            like2017_list.append(prime)
        
    return like2017_list
        
    
    
def main():
    #input
#    Q1 = 1
#    LR1 = [[3,7]]
#    
#    Q2 = 4
#    LR2 = [[13, 13],
#                [7, 11],
#                [7, 11],
#                [2017, 2017]]
#    
#    
#    Q = Q2
#    LR = LR2
    
    Q = int(eval(input()))
    LR = []
    for i in range(Q):
        LR.append(list(map(int, input().split())))

    # 1. find 2017-like number
    MAX_Q = 10**5
    
    like2017_list = judge_prime(MAX_Q)

    
    # judge
    csum = [0]*(MAX_Q+1)
    i = 0
    cnt = 0
    for like2017 in like2017_list:
        while i < like2017:
            csum[i] = cnt
            i += 1
        cnt += 1
    for i in range(like2017_list[-1], MAX_Q+1):
        csum[i] = cnt
        
    
    for i in range(Q):
        print((csum[LR[i][1]] - csum[LR[i][0]-1]))


    
if __name__ == "__main__":
    main()

# Optimized solution
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from bisect import bisect_left, bisect_right

# 半開区間[lower, upper)の素数のリストを作成する
def make_prime_list(lower:int, upper:int) -> list:
    
    # 素数リストの初期化    
    isPrime = [True]*upper
    primeList = []
    
    # 区間内の数字が0,1のみならここで終了
    if upper <= 2:
        return primeList
    
    # 区間内の数字に2以上のものがあるとき
    isPrime[0] = False
    isPrime[1] = False
    
    # エラトステネスの篩の処理
    for n in range(2,int(sqrt(upper))+2):
        if isPrime[n]:
            res=2*n
            while res<upper:
                isPrime[res] = False
                res += n
    
    # 区間内の素数を抽出
    for n in range(lower,upper):
        if isPrime[n]:
            primeList.append(n)
        
    return primeList

q = ni()
query = [tuple(li()) for _ in range(q)]

prime_list = set(make_prime_list(2,10**5+1))

like2017 = []

for i in range(3, 10**5, 2):
    if (i in prime_list) and ((i+1)//2 in prime_list):
        like2017.append(i)
        
for l,r in query:
    print((bisect_right(like2017, r) - bisect_left(like2017, l)))
# Original solution
import math
Q = int(eval(input()))
lr = [list(map(int, input().split())) for i in range(Q)]

max_l = max(lr, key=lambda x:x[1])[1]

a = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = [x for x in a[m:] if x%a[m-1] != 0]
    a = a[:m]
    a.extend(b)
    m += 1
    if m > len(a):
        break

like2017 = [3]
for i in range(5,max_l+1,4):
    for j in a:
        if not ((i % j != 0 or i in a) and ((i+1)/2 % j != 0 or (i+1)/2 in a)):
            break
        if j == a[-1]:
            like2017.append(i)

for i in range(Q):
    print((len(list([x for x in like2017 if lr[i][0] <= x <= lr[i][1]]))))


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

max_l = max(lr, key=lambda x:x[1])[1]

prime = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = [x for x in prime[m:] if x%prime[m-1] != 0]
    prime = prime[:m]
    prime.extend(b)
    m += 1
    if m > len(prime):
        break

like2017 = {-1:0,1:0}
for i in range(3,max_l+2,2):
    k = 0
    for j in prime:
        if (i%j == 0 or ((i+1)/2)%j == 0) and i != j and (i+1)/2 != j:
            k += 1
            break
    if k == 0:
        like2017[i] = like2017[i-2] + 1
    else:
        like2017[i] = like2017[i-2]


for i in range(Q):
    print((like2017[lr[i][1]]-like2017[lr[i][0]-2]))
# Original solution
INFTY = 10**5+1
P = [1 for _ in range(INFTY)]
P[0]=P[1]=0
for i in range(2,int(INFTY**0.5)+1):
    for j in range(i*i,INFTY,i):
        P[j] = 0
R = [0 for _ in range(INFTY)]
for i in range(INFTY):
    if i%2==1:
        if P[i]==1 and P[(i+1)//2]==1:
            R[i] = 1
A = [0 for _ in range(INFTY+1)]
for i in range(INFTY):
    A[i+1] = A[i]+R[i]
Q = int(eval(input()))
for _ in range(Q):
    l,r = list(map(int,input().split()))
    print((A[r+1]-A[l]))

# Optimized solution
P = [1 for _ in range(10**5)]
P[0]=0
P[1]=0
for i in range(2,int((10**5)**0.5)+1):
    for j in range(i*i,10**5,i):
        P[j]=0
Q = []
for i in range(3,10**5,2):
    if P[i]==1 and P[(i+1)//2]==1:
        Q.append(i)
A = [0 for _ in range(10**5+1)]
for q in Q:
    A[q] = 1
for i in range(1,10**5+1):
    A[i] += A[i-1]
Q = int(eval(input()))
for _ in range(Q):
    l,r = list(map(int,input().split()))
    print((A[r]-A[l-1]))
# Original solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

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

    return True

Q = inp()
cnt = [False] * (10**5+10)
table = [False] * (10**5+10)
for i in range(1,10**5+5):
    cnt[i] = is_prime(i)
for i in range(1,10**5+5):
    table[i] = i%2 and cnt[i] and cnt[(i+1)//2]
res = [0] * (10**5+5)
for i in range(10**5+4):
    tmp = 1 if table[i] else 0
    res[i+1] = res[i] + tmp
# print(res[:20])
for _ in range(Q):
    a,b = inpl()
    print((res[b+1] - res[a]))

# Optimized solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

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

    return True
n = 10**5+10
Q = inp()
ch = [False] * (n+5)
for i in range(1,n):
    if is_prime(i):
        ch[i] = True
table = [0] * (n+5)
for i in range(1,n):
    tmp = 0
    if i%2 and ch[i] and ch[(i+1)//2]:
        tmp = 1
    table[i] = table[i-1] + tmp
for _ in range(Q):
    a,b = inpl()
    print((table[b] - table[a-1]))
# Original solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

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

    return True
n = 10**5+10
Q = inp()
ch = [False] * (n+5)
for i in range(1,n):
    if is_prime(i):
        ch[i] = True
table = [0] * (n+5)
for i in range(1,n):
    tmp = 0
    if i%2 and ch[i] and ch[(i+1)//2]:
        tmp = 1
    table[i] = table[i-1] + tmp
for _ in range(Q):
    a,b = inpl()
    print((table[b] - table[a-1]))

# Optimized solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

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

    return True
a = [0] * 100100
for i in range(1,100010):
    tmp = 0
    if is_prime(i) and is_prime((i+1)//2):
        tmp = 1
    a[i] = a[i-1] + tmp
q = inp()
for _ in range(q):
    l,r = inpl()
    print((a[r] - a[l-1]))
# Original solution
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(eval(input()))
def F(): return float(eval(input()))
def S(): return eval(input())
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def sieve(n):
    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 [i for i in range(n+1) if is_prime[i]]

def resolve():
    Q = I()
    lr = [LI() for _ in range(Q)]

    r_max = max([i[1] for i in lr])
    primes = sieve(r_max)

    acc = [0]*(r_max+2)
    for i in range(r_max+1):
        if i in primes and (i+1)//2 in primes:
            acc[i+1] = acc[i] + 1
        else:
            acc[i+1] = acc[i]

    for i in lr:
        print((acc[i[1]+1]-acc[i[0]]))

if __name__ == '__main__':
    resolve()

# Optimized solution
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(eval(input()))
def F(): return float(eval(input()))
def S(): return eval(input())
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def sieve(n):
    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 [i for i in range(n+1) if is_prime[i]]

def resolve():
    Q = I()
    lr = [LI() for _ in range(Q)]

    r_max = max([i[1] for i in lr])
    primes = set(sieve(r_max))

    acc = [0]*(r_max+2)
    for i in range(r_max+1):
        if i in primes and (i+1)//2 in primes:
            acc[i+1] = acc[i] + 1
        else:
            acc[i+1] = acc[i]

    for i in lr:
        print((acc[i[1]+1]-acc[i[0]]))

if __name__ == '__main__':
    resolve()