CodeEff/ECCO huggingface dataset:
# Original solution
from itertools import accumulate
Q = int(eval(input()))

def sieve(n):
    if n == 0:
        return [False]

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

MAX = 10 ** 5
is_prime = sieve(MAX)
cnt = [0] * (MAX + 1)
for i in range(MAX + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        cnt[i] = 1
cnt = list(accumulate(cnt))

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


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

n = 10 ** 5 + 2
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, n + 1):
    if not is_prime[i]:
        continue

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

like = [False] * (n + 1)
for i in range(n):
    like[i] = is_prime[i] and is_prime[(i + 1) // 2]

cumsum = [0] * (n + 1)
for i in range(n):
    cumsum[i + 1] = cumsum[i] + like[i]

for l, r in X:
    print((cumsum[r + 1] - cumsum[l]))
# Original solution
def l(): return list(map(int, input().split()))
def m(): return list(map(int, input().split()))

def sieve(n): # エラトステネスの篩ですよ
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]

def main():
  q = int(eval(input()))
  for i in range(q):
    l, r = m()
    prime = sieve(r+1)
    # print(prime)
    likp = [0]*r
    for i in prime:
      if (i+1) // 2 in prime:
        likp[i-1] = 1
    # print(likp)
    sm = [0]*(r+1)
    for i in range(r):
      sm[i+1] = sm[i] + likp[i]
    # print(sm)
    print((sm[r] - sm[l-1]))
   


if __name__ == '__main__':
  main()

# Optimized solution
def l(): return list(map(int, input().split()))
def m(): return list(map(int, input().split()))

def sieve(n): # エラトステネスの篩ですよ
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]

def main():
  q = int(eval(input()))
  l , r = [0]*q, [0]*q
  for i in range(q):
    l[i], r[i] = m()
  rr = max(r) 
  prime = sieve(rr+1)
  # print(prime)
  likp = [0]*rr
  for i in prime:
    if (i+1) // 2 in prime:
      likp[i-1] = 1
  # print(likp)
  sm = [0]*(rr+1)
  for i in range(rr):
    sm[i+1] = sm[i] + likp[i]
  # print(sm)
  for i in range(q):
    print((sm[r[i]] - sm[l[i]-1]))
   


if __name__ == '__main__':
  main()
# Original solution
a=[0 for i in range(10**5+5)]
for i in range(3,10**5+3,2):
    for j in range(3,int(i**0.5)+1,2):
        if i%j==0 and j!=i:
            break
    else:
        a[i]=1
a[3],a[2]=1,1
b=[0 for i in range(10**5+5)]
for i in range(3,10**5+3,2):
    b[i]=a[i] and a[(i+1)//2]
c=[0]
for i in range(len(b)):
    c.append(c[i]+b[i])
for i in range(int(eval(input()))):
    l,r=list(map(int,input().split()))
    print((c[r+1]-c[l]))

# Optimized solution
a=[0 for i in range(10**5+3)]
b=[1 for i in range(10**5+3)]
for i in range(2,10**5+3):
    if b[i]==1:
        for j in range(2*i,10**5+3,i):
            b[j]=0
b[0]=0
b[1]=0
for i in range(1,10**5+3,2):
    a[i]=b[i] and b[(i+1)//2]
e=[a[0]]
for i in range(1,10**5+3):
    e.append(a[i]+e[i-1])
#print(e)
for i in range(int(eval(input()))):
    l,r=list(map(int,input().split()))
    print((e[r]-e[l-1]))
# Original solution
Q = int(eval(input()))
lr = []
for i in range(Q):
   lr.append(list(map(int, input().split())))

N = 100000
like_number = [3]
prime_number = [2]
for i in range(3, N, 2):
   flag = 0
#   for j in range(3, int(i**0.5)+1, 2):
   for j in prime_number:
      if j > int(i**0.5)+1:
         break
      elif i%j == 0:
         flag = 1
         break
   if flag == 0:
      prime_number.append(i)
      if ((i+1)/2)%2 == 1:
         if (i+1)/2 in prime_number:
            like_number.append(i)
         

for i in range(Q):
   count = 0
   for j in like_number:
      if lr[i][1] >= j:
         if lr[i][0] <= j:
            count = count + 1
      else:
         break
   print(count)


# Optimized solution
def main():
    Q = int(eval(input()))
    L = [0 for _ in range(Q)]
    R = [0 for _ in range(Q)]
    for i in range(Q):
        L[i], R[i] = list(map(int, input().split()))

    N = 100000
    sosu = [1 for _ in range(N)]
    sosu[0] = 0
    for i in range(1,int(N**0.5)):
        k = i+1
        if sosu[i] == 1:
            j = k + k
            while j <= N:
                sosu[j-1] = 0
                j = j+k
    like = [0 for _ in range(N)]
    for i in range(2, N, 2):
        if sosu[i]==1 and sosu[(i+2)//2-1]==1:
            like[i] = 1
    like_wa = [0 for _ in range(N+1)]
    for i in range(N):
        like_wa[i+1] = like_wa[i] + like[i]

    for i in range(Q):
        print((like_wa[R[i]] - like_wa[L[i]-1]))

if __name__ == '__main__':
    main()
# Original solution
n = 10**5
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)))
primes={i for i in primes if (i+1)//2 in primes}
q=int(eval(input()))
for i in range(q):
    a,b=list(map(int, input().split()))
    print((len(set(range(a,b+1))&primes)))

# Optimized solution
import bisect
n = 10**5
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)))
primes=[i for i in primes if (i+1)//2 in primes]
q=int(eval(input()))
for i in range(q):
    a,b=list(map(int, input().split()))
    print((bisect.bisect_right(primes, b)-bisect.bisect_left(primes, a)))
# Original solution
m = 100010
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]
a = primes(m * 2+ 100)
n = int(eval(input()))

from bisect import bisect_left
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def do(x):
    if x in a and (x+1)//2 in a:
        return True
dat = [-1] * m
count = 0
for i in range(len(a)):
    if a[i] > m:
        break
    if do(a[i]):
        count += 1
    dat[a[i]] = count
c = -1
for i in range(m):
    if dat[i] != -1:
        c = dat[i]
    else:
        dat[i] = c
dat[0] = dat[1] = 0

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


# Optimized solution
m = 100010

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        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]]

a = primes(m * 2 + 100)
n = int(eval(input()))

from bisect import bisect_left
def index(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    return False

def do(x):
    if index(a, x) and index(a, (x + 1) // 2):
        return True

dat = [-1] * m
count = 0
for i in range(len(a)):
    if a[i] > m:
        break
    if do(a[i]):
        count += 1
    dat[a[i]] = count
c = -1
for i in range(m):
    if dat[i] != -1:
        c = dat[i]
    else:
        dat[i] = c
dat[0] = dat[1] = 0

for _ in range(n):
    l, r = list(map(int, input().split()))
    print((dat[r] - dat[l - 1]))
# Original solution
import bisect

# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(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]


primes = eratosthenes(10 ** 5+1)
like2017 = list([x for x in primes if (x+1)/2 in primes])
num_like2017 = len(like2017)

Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    left = bisect.bisect_left(like2017, l)
    right = num_like2017 - bisect.bisect_right(like2017, r)

    print((num_like2017 - left - right))




# Optimized solution
# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(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()))
LR = [list(map(int, input().split())) for i in range(Q)]

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

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

for l, r in LR:
    print((ruiseki[r] - ruiseki[l-2]))
# Original solution
def is_prime(q):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(5, q-1, q)*pow(7, q-1, q) == 1
    
s = [561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831]
b = [5,7]
for i in range(2,10**5):
  if i in s:
    continue
  if is_prime(i):
    b.append(i)

a = set([2*i-1 for i in b])
b = set(b)
chk = sorted(list(a&b))
 
from bisect import bisect,bisect_left
import sys
input = sys.stdin.readline
 
q = int(eval(input()))
for i in range(q):
  l,r = list(map(int,input().split()))
  print((bisect(chk,r)-bisect_left(chk,l)))

# Optimized solution
def is_prime(q):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(5, q-1, q)*pow(7, q-1, q) == 1
  
def main():
  s = set([561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831])
  b = [5,7]
  for i in range(2,10**5):
    if i in s:
      continue
    if is_prime(i):
      b.append(i)

  a = set([2*i-1 for i in b])
  b = set(b)
  chk = sorted(tuple(a&b))

  from bisect import bisect,bisect_left
  import sys
  input = sys.stdin.readline

  q = int(eval(input()))
  for i in range(q):
    l,r = list(map(int,input().split()))
    print((bisect(chk,r)-bisect_left(chk,l)))
    
if __name__ == '__main__':
    main()
# Original solution
Q = int(eval(input()))
query = [list(map(int, input().split())) for _ in range(Q)]

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

prime = []
ans = [0]*100001
sum_a = [0]*100001
for n in range(1, 100000+1):
  if is_prime(n) and is_prime((n+1)//2):
    if n != 2:
      prime.append(n)
      ans[n] = 1
  sum_a[n] = sum_a[n-1] + ans[n]

for l, r in query:
  print((sum_a[r] - sum_a[l-1]))

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

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

prime = [0]*100001
sum_a = [0]*100001
for n in range(1, 100000+1):
  if is_prime(n) and is_prime((n+1)//2):
    prime[n] = 1
  sum_a[n] = sum_a[n-1] + prime[n]

for l, r in query:
  print((sum_a[r] - sum_a[l-1]))
# Original solution
#!/usr/bin/env python3
import sys
from bisect import bisect_right


def cal_prime(N):
    prime_list = set()
    ans_list = set()
    for i in range(2, N):
        flag = True
        for j in range(2, int(i**0.5)+1):
            if i % j == 0:
                flag = False
                break
        if flag:
            prime_list.add(i)
            if i > 2 and (i+2) // 2 in prime_list:
                ans_list.add(i)
    return sorted(ans_list)


def main():
    Q = int(eval(input()))
    ans_list = cal_prime(10**5)

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


if __name__ == '__main__':
    main()


# Optimized solution
def cal_primes(N):
    candidate = [*list(range(2, N+1))]
    primes = []

    while candidate[0]**2 <= N:
        primes.append(candidate[0])
        candidate = [*[x for x in candidate if x % candidate[0] != 0]]
    
    primes.extend(candidate)
    return primes

Q = int(eval(input()))
primes = set(cal_primes(10**5))
# print(primes)
res = [0] * (10**5+1)
for i in range(1,10**5+1):
    #print(i)
    if i%2==1 and i in primes and (i+1)//2 in primes:
        res[i] = res[i-1] + 1
    else:
        res[i] = res[i-1]
#print(res)
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((res[r]-res[l-1]))
# Original solution
def factorization(n):
 p=2
 fcr=[]
 while p*p<=n:
  while n%p==0:
   fcr.append(p)
   n//=p
  p+=1
 if n>1:
  fcr.append(n)
 return fcr

q=int(eval(input()))

cnt=1
p_list=[1]
q_list=[0]
for i in range(3,10**5+1,2):
 a=factorization(i)
 b=factorization((i+1)//2)

 if len(a)==len(b)==1:
  cnt+=1
  q_list.append(1)
 else:
  q_list.append(0)

 p_list.append(cnt)

for i in range(q):
 l,r=list(map(int,input().split()))

 c=p_list[r//2]-p_list[l//2]
 if q_list[l//2]==1:
  print((c+1))
 else:
  print(c)

# Optimized solution
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

# return p_list
 return is_p

q=int(eval(input()))

lim=10**5+1
is_p=eratosthenes(lim)

#print(is_p)

b=[0]
for i in range(1,lim+1):
 if is_p[i-1]==1 and is_p[i//2]==1:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

#print(b)

for i in range(q):
 l,r=list(map(int,input().split()))
 print((b[r+1]-b[l]))
# Original solution
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

# return p_list
 return is_p

q=int(eval(input()))

lim=10**5+1
is_p=eratosthenes(lim)

#print(is_p)

b=[0]
for i in range(1,lim+1):
 if is_p[i-1]==1 and is_p[i//2]==1:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

#print(b)

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

# Optimized solution
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(eval(input()))

b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

for i in range(q):
 l,r=list(map(int,input().split()))
 print((b[r+1]-b[l]))
# Original solution
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(eval(input()))

'''
b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])
'''
a = [0] * (10**5+2)
for i in range(3, 10**5+1, 2):
    if is_p[i] and is_p[(i+1)//2]:
        a[i] = 1
for i in range(1, 10**5+1):
    a[i+1] += a[i]

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

# Optimized solution
def eratosthenes(n):
 is_p=[1]*n
# p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
#   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p#, p_list

lim=10**5+1
#is_p, p_list=eratosthenes(lim)
is_p=eratosthenes(lim)

q=int(eval(input()))

'''
b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])
'''
a = [0] * (10**5+2)
for i in range(3, 10**5+1, 2):
    if is_p[i] and is_p[(i+1)//2]:
        a[i] = 1
for i in range(1, 10**5+1):
    a[i+1] += a[i]

for i in range(q):
 l,r=list(map(int,input().split()))
# print(b[r+1]-b[l])
 print((a[r]-a[l-1]))
# Original solution
import sys
import bisect
from functools import lru_cache

input = sys.stdin.readline


@lru_cache(maxsize=None)
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 = [[int(x) for x in input().split()] for _ in range(Q)]

    sosu = []
    for i in range(1, 10 ** 5 + 1):
        if is_prime(i) and is_prime((i + 1) // 2):
            sosu.append(i)

    for l, r in lr:
        li = bisect.bisect_left(sosu, l)
        ri = bisect.bisect_right(sosu, r)
        print((ri - li))









if __name__ == '__main__':
    main()


# Optimized solution
import sys
import bisect

input = sys.stdin.readline


def get_primes(n):
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i:: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(eval(input()))
    lr = [[int(x) for x in input().split()] for _ in range(Q)]

    P = get_primes(10 ** 5 + 1)
    setP = set(P)
    like = []
    for p in P:
        if (p + 1) // 2 in setP:
            like.append(p)


    for l, r in lr:
        li = bisect.bisect_left(like, l)
        ri = bisect.bisect_right(like, r)
        print((ri - li))


if __name__ == '__main__':
    main()
# Original solution
def primes(a):
    if a==2 or a%2 != 0:
        return True
    return False

P=[0]*100001

for i in range(2,100001):
    if P[i]==0 and primes(i):
        for j in range(i+i,100001,i):
            P[j] = 1

C=[0]*100002

for i in range(3,100000,2):
    if P[i]==0 and P[int((i+1)/2)]==0:
        C[i]+=1
for i in range(3,100000):
    C[i]+=C[i-1]

N= int(eval(input()))

L=[]
R=[]
for i in range(N):
    l,r=list(map(int, input().split()))
    L.append(l)
    R.append(r)

for i in range(N):
    print((C[R[i]]-C[L[i]-1]))


# Optimized solution
def primes(a):
    if a==2 or a%2 != 0:
        return True
    return False

P=[0]*100000

for i in range(2,100000):
    if P[i]==0 and primes(i):
        for j in range(i+i,100000,i):
            P[j] = 1

C=[0]*100000

for i in range(3,100000,2):
    if P[i]==0 and P[int((i+1)/2)]==0:
        C[i]+=1
for i in range(3,100000):
    C[i]+=C[i-1]

N= int(eval(input()))

L=[]
R=[]
for i in range(N):
    l,r=list(map(int, input().split()))
    L.append(l)
    R.append(r)

for i in range(N):
    print((C[R[i]]-C[L[i]-1]))
# Original solution
#!/usr/bin python3
# -*- coding: utf-8 -*-

n = 10**5
#primes = set(range(3, n+1, 2))|set([2])
primes = set(range(3, n+1, 2)) #偶数は除く
for i in range(3, int(n**0.5+1)):
    primes.difference_update(list(range(i*3, n+1, i*2)))
primes = list(primes)

Likes = [0] * (n+1)
cnt = 0
for i in primes:
    if (i+1)//2 in primes or (i+1)//2==2:
        Likes[i]=1
for i in range(1,n):
    Likes[i]+=Likes[i-1]

def main():
    Q = int(eval(input()))
    for q in range(Q):
        l,r = list(map(int,input().split()))
        print((Likes[r]-Likes[l-1]))

if __name__ == '__main__':
    main()

# Optimized solution
#!/usr/bin python3
# -*- coding: utf-8 -*-
import sys
input=sys.stdin.readline
n = 10**5
#primes = set(range(3, n+1, 2))|set([2])
primes = set(range(3, n+1, 2)) #偶数は除く
for i in range(3, int(n**0.5+1)):
    primes.difference_update(list(range(i*3, n+1, i*2)))
primes.add(2)

Likes = [0] * (n+1)
cnt = 0
for i in range(1,n+1,2):
    Likes[i-1]=Likes[i-2]
    x = (i+1)//2
    if i in primes and (x in primes or x==2):
        Likes[i]=Likes[i-1] + 1
    else:
        Likes[i]=Likes[i-1]

def main():
    Q = int(eval(input()))
    for q in range(Q):
        l,r = list(map(int,input().split()))
        print((Likes[r]-Likes[l-1]))

if __name__ == '__main__':
    main()
# Original solution
prime = [True]*((10**5)+1)
prime[0]=False
prime[1]=False
for i in range(2,10**3):
  if i*i>10**5:
    break
  if prime[i]:
    for j in range(i,10**5):
      if i*j>10**5:
        break
      prime[i*j]=False

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

count = 0
csum = [0]*((10**5)+1)
for i in range((10**5)+1):
  if prime2017[i]:
    count+=1
  csum[i]=count

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

# Optimized solution
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                r[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    prime = Eratosthenes(10**5)
    prime_2017 = [False]*(10**5+1)
    for i in range(3,10**5+1,2):
        if prime[i]:
            prime_2017[i] = prime[(i+1)//2]

    cnt = [0]*(10**5+1)
    nxt = 0

    for i in range(1,10**5+1):
        if prime_2017[i]:
            nxt += 1
        cnt[i] = nxt

    Q = I()
    for _ in range(Q):
        l,r = LI()
        print((cnt[r] - cnt[l-1]))

            


if __name__ == "__main__":
    main()
# Original solution
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

Q = I()
lr = [LI() for i in range(Q)]

import math

def sieve_of_eratosthenes(n):
    prime_list = []  # n以下の素数のリスト
    A = [1]*(n+1)    # A[i] = iが素数なら1,その他は0
    A[0] = A[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if A[i]:
            prime_list.append(i)
            for j in range(i**2,n+1,i):
                A[j] = 0
    for i in range(math.floor(math.sqrt(n)),n+1):
        if A[i] == 1:
            prime_list.append(i)
    return A

prime = sieve_of_eratosthenes(10**5)
prime_like_2017 = [0]*(10**5+1)
prime_like_2017[3] = 1

for i in range(3,10**5+1):
    if prime[i] == 0:
        continue
    elif i == 2:
        continue
    elif i == 3:
        prime_like_2017[i] = 1
    elif i % 4 == 3:
        continue
    else:
        if prime[(i+1)//2] == 1:
            prime_like_2017[i] = 1

from itertools import accumulate

P = list(accumulate(prime_like_2017))  # P[i] = iまでに2017に似た数が何個あるか

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

# Optimized solution
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


import math


def sieve_of_eratosthenes(n):
    prime_list = []  # n以下の素数のリスト
    A = [1]*(n+1)    # A[i] = iが素数なら1,その他は0
    A[0] = A[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if A[i]:
            prime_list.append(i)
            for j in range(i**2,n+1,i):
                A[j] = 0
    for i in range(math.floor(math.sqrt(n))+1,n+1):
        if A[i] == 1:
            prime_list.append(i)
    return prime_list,A


prime_list,A = sieve_of_eratosthenes(10**5)

B = [0]*(10**5+1)
for p in prime_list:
    if p == 2:
        continue
    else:
        if A[(p+1)//2] == 1:
            B[p] = 1

from itertools import accumulate

C = list(accumulate(B))

Q = I()
for i in range(Q):
    l,r = MI()
    print((C[r]-C[l-1]))