CodeEff/ECCO huggingface dataset:
# Original solution
from math import ceil, sqrt

n = 10**5+200
hurui = [i for i in range(n+1)]
for i in range(2,ceil(sqrt(n))+1):
    for j in range(2,ceil(sqrt(i))+1):
        if i==2:
            continue
        if i%j == 0:
            break
    else:
        for k in range(i+i,n,i):
            if hurui[k] != k:
                continue
            hurui[k] = 0
    continue

hurui = [bool(i) for i in hurui]
poi = [False]*(n+1)
for i in range(n+1):
    # print(i)
    poi[i] = (i % 2 == 1 and hurui[i] and hurui[(i+1)//2])
poi[1] = False
#print(poi)
sa = [0]
for i in range(n+1):
    sa.append(sa[i]+poi[i])
#print(sa[:10])

#print(poi[2017])

q = int(eval(input()))
lr = [tuple(map(int,input().split())) for i in range(q)]
for li,ri in lr:
    print((sa[ri+1]-sa[li]))


# Optimized solution
from math import ceil, sqrt


def eratosthenes(n):
    hurui = [i for i in range(n + 1)]
    for i in range(2, ceil(sqrt(n)) + 1):
        for j in range(2, ceil(sqrt(i)) + 1):
            if i == 2:
                continue
            if i % j == 0:
                break
        else:
            for k in range(i + i, n, i):
                if hurui[k] != k:
                    continue
                hurui[k] = 0
        continue
    return hurui


n = 10**5 + 200
hurui = eratosthenes(n)
hurui = [bool(i) for i in hurui]
poi = [False] * (n + 1)
for i in range(n + 1):
    poi[i] = (i % 2 == 1 and hurui[i] and hurui[(i + 1) // 2])
poi[1] = False
sa = [0]
for i in range(n + 1):
    sa.append(sa[i] + poi[i])
q = int(eval(input()))
lr = [tuple(map(int, input().split())) for i in range(q)]
for li, ri in lr:
    print((sa[ri + 1] - sa[li]))
# Original solution
def check(i):
    num=int(i**0.5)
    if i==1:return 0
    if i==2:return 1
    for j in range(2,num+1):
        if i%j==0:break

    else:return 1
    return 0
q=int(eval(input()))
lr=[list(map(int,input().split())) for i in range(q)]

L=[0]*(10**5+1)#0~100000
for i in range(10**5+1):
    if i%2==0:
        L[i]=L[i-1]
    else:
        L[i]=L[i-1]+check(i)*check((i+1)//2)

for l,r in lr:
    cnt=L[r]-L[l-1]
    print(cnt)

# Optimized solution
def check_prime(k):
    '''
    素数の時1、合成数の時0を返す
    '''
    if k == 1:return 0
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:return 0
    return 1

q = int(eval(input()))
lr = []
l_min = 10 ** 9
r_max = 0
for i in range(q):
    l, r = list(map(int,input().split()))
    lr.append((l, r))
    if l < l_min:l_min = l
    if r > r_max:r_max = r

pre_cal = [0] * (r_max - l_min + 2)
dic = {}#一度素数と判定したもの
for num in range(l_min, r_max + 1):
    pre_cal[num - l_min + 1] = pre_cal[num - l_min]
    if num % 2 == 0:continue
    if not check_prime(num):continue
    dic[num] = 1
    temp = (num + 1) // 2

    if dic.get(temp, 0):
        pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1
    else:
        if check_prime(temp):
            dic[temp] = 1
            pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1

for l, r in lr:
    ans = pre_cal[r - l_min + 1] - pre_cal[l - l_min]
    print(ans)

#print(pre_cal)
# Original solution
Q = int(eval(input()))

from functools import lru_cache
@lru_cache(maxsize=None)
def is_prime(n: int):
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    for p in range(3, int(n**0.5)+1, 2):
        if n % p == 0:
            return False
    return True

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

from bisect import bisect_left, bisect_right
for _ in range(Q):
    l, r = list(map(int, input().split()))
    li = bisect_left(like_2017s, l)
    ri = bisect_right(like_2017s, r)
    print((ri-li))

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

import math
def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)
    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

primes = sieve_of_erastosthenes(10**5)
likes = []
for i in range(3, 10**5, 2):
    if primes[i] and primes[(i+1)//2]:
        likes.append(i)

from bisect import bisect_left, bisect_right

for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((bisect_right(likes, r) - bisect_left(likes, l)))
# Original solution
import math
import bisect
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

prime=set([2])
for i in range(3,100001):
    if i%2!=0 and is_prime(i):
        prime.add(i)

sim_prime=[]
for p in prime:
    if (p+1)//2 in prime:
        sim_prime.append(p)
sim_prime.sort()


q=int(eval(input()))
ans_list=[]
for i in range(q):
    l,r=list(map(int,input().split()))
    l_idx=bisect.bisect_left(sim_prime,l)
    r_idx=bisect.bisect_left(sim_prime,r)
    if sim_prime[min(r_idx,len(sim_prime)-1)]==r:
        r_idx+=1
    ans_list.append(r_idx-l_idx)

for g in range(len(ans_list)):
    print((ans_list[g]))

# Optimized solution
import math
import bisect
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

prime=set([2])
for i in range(3,100001):
    if i%2!=0 and is_prime(i):
        prime.add(i)

sim_prime=[]
for p in prime:
    if (p+1)//2 in prime:
        sim_prime.append(p)
sim_prime.sort()


q=int(eval(input()))
ans_list=[]
for i in range(q):
    l,r=list(map(int,input().split()))
    l_idx=bisect.bisect_left(sim_prime,l)
    r_idx=bisect.bisect_left(sim_prime,r+1)
    ans_list.append(r_idx-l_idx)

for g in range(len(ans_list)):
    print((ans_list[g]))
# Original solution
def gen_is_prime(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]]
    return is_prime


if __name__ == "__main__":
    max_n = 10 ** 5
    is_prime = gen_is_prime(max_n)

    is_like_2017 = [False] * (max_n + 1)
    for i in range(max_n + 1):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            is_like_2017[i] = True

    sum_is_like_2017 = [0] * (max_n + 2)
    for i in range(max_n + 1):
        sum_is_like_2017[i + 1] = sum_is_like_2017[i] + is_like_2017[i]

    q = int(eval(input()))
    lr = [list(map(int, input().split())) for _ in range(q)]
    for l, r in lr:
        print((sum_is_like_2017[r + 1] - sum_is_like_2017[l]))


# Optimized solution
from itertools import accumulate


def gen_primes(n: int) -> set:
    if n < 2:
        return set()
    is_prime = [True] * n
    for i in range(3, n, 2):
        if is_prime[i]:
            is_prime[i * i:: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if is_prime[i]}


if __name__ == "__main__":
    max_n = 10 ** 5 + 1
    primes = gen_primes(max_n)

    is_like_2017 = [True if i in primes and (i + 1) // 2 in primes else False for i in range(max_n)]
    sum_is_like_2017 = tuple(accumulate(is_like_2017))

    q = int(eval(input()))
    lr = [list(map(int, input().split())) for _ in range(q)]
    for l, r in lr:
        print((sum_is_like_2017[r] - sum_is_like_2017[l - 1]))
# Original solution
from itertools import accumulate


def get_primes_til(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, int(n ** .5) + 1):
        for j in range(2 * i, n + 1, i):
            primes[j] = False
    return primes


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([int(primes[i] and primes[(i + 1) // 2]) for i in range(N_MAX + 1)]))
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((is_2017_like[r] - is_2017_like[l - 1]))


# Optimized solution
from itertools import accumulate


def get_prime_numbers_til(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_MAX = 10 ** 5
primes = get_prime_numbers_til(N_MAX)
is_2017_like = list(accumulate([1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(N_MAX + 1)]))
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((is_2017_like[r] - is_2017_like[l - 1]))
# Original solution
from itertools import accumulate


def get_primes_til(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, int(n ** .5) + 1):
        for j in range(2 * i, n + 1, i):
            primes[j] = False
    return {i for i in range(2, n + 1) if primes[i]}


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([i in primes and (i + 1) // 2 in primes for i in range(N_MAX + 1)]))
for _ in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    print((is_2017_like[r] - is_2017_like[l - 1]))


# Optimized solution
from itertools import accumulate


def get_primes_til(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** .5) + 1):
        if is_prime[i]:
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return {i for i in range(2, n + 1) if is_prime[i]}


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([i in primes and (i + 1) // 2 in primes for i in range(N_MAX + 1)]))
for _ in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    print((is_2017_like[r] - is_2017_like[l - 1]))
# Original solution
# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize

# ===CODE===
q = int(eval(input()))

condition = 10 ** 5

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

kodoku = {2}

for i in range(3, condition + 5, 2):
    lim = i ** (1 / 2)
    flg = True
    for j in range(2, int(lim)+1):
        # if div > lim:
        #     break
        if i % j == 0:
            flg = False
            break

    if flg:
        kodoku.add(i)

ruisekiwa = [0] * (condition + 5)

for i in range(3, condition + 5):
    ruisekiwa[i] = ruisekiwa[i - 1]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1

for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]
    print(ans)


# Optimized solution
# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize

# ===CODE===
q = int(eval(input()))

condition = 10 ** 5

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

kodoku = {2}
kodoku_2 = [2]

for i in range(3, condition + 5, 2):
    lim = i ** (1 / 2)
    flg = True
    for div in kodoku_2:
        if div > lim:
            break
        if i % div == 0:
            flg = False
            break

    if flg:
        kodoku.add(i)
        kodoku_2.append(i)

ruisekiwa = [0] * (condition + 5)

for i in range(3, condition + 5):
    ruisekiwa[i] = ruisekiwa[i - 1]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1

for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]
    print(ans)
# Original solution
import math

def is_prime(n):
    if n == 1:
        return False
    if not isinstance(n,int):
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

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

list_2017_similar=[]
for i in range(1,100000):
    if is_prime(i) == True and is_prime(int((i+1)/2)) == True and i != 2:
        list_2017_similar.append(i)

for i in range(Q):
    cnt=0
    for j in list_2017_similar:
        if L[i] <= j <= R[i]:
            cnt += 1
    print(cnt)


# Optimized solution
import math

def is_prime(n):
    if n == 1:
        return False
    if not isinstance(n,int):
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

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

list_2017_similar_num=[0]
for i in range(1,100001):
    if i % 2 == 0:
        list_2017_similar_num.append(list_2017_similar_num[i-1])
    else:
        if is_prime(i) == True and is_prime(int((i+1)/2)) == True:
            list_2017_similar_num.append(list_2017_similar_num[i-1]+1)
        else:
            list_2017_similar_num.append(list_2017_similar_num[i-1])

for i in range(Q):
    print((list_2017_similar_num[R[i]] - list_2017_similar_num[L[i]-1]))
# Original solution
from itertools import accumulate
def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True
def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x+1)//2):
        return True
q=int(eval(input()))
l=[0]*(10**5+1)
for i in range(1,10**5+1):
    if like2017(i):
        l[i]=1
acl = list(accumulate(l))
for i in range(q):
    l,r=list(map(int,input().split()))
    print((acl[r]-acl[l-1]))

# Optimized solution
from itertools import accumulate
import sys
input=sys.stdin.readline
def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True
def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x+1)//2):
        return True
q=int(eval(input()))
l=[0]*(10**5+1)
for i in range(1,10**5+1):
    if like2017(i):
        l[i]=1
acl = list(accumulate(l))
for i in range(q):
    l,r=list(map(int,input().split()))
    print((acl[r]-acl[l-1]))
# Original solution
import sys
input = sys.stdin.readline

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(100000)
resemble = []
for i in a:
    if i == 2 or (i+1)//2 not in a:
        pass
    else:
        resemble.append(i)
n = int(eval(input()))
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = list(map(int,input().split()))
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print((q[i]))

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

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 is_prime
a = primes(100000)
resemble = []
for i in range(len(a)):
    if a[i]:
        if a[(i+1)//2]:
            resemble.append(i)
n = int(eval(input()))
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
#print(ans[:30])
for i in range(n):
    l,r = list(map(int,input().split()))
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print((q[i]))
# Original solution
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 is_prime
a = primes(100000)
resemble = []
for i in range(len(a)):
    if a[i]:
        if a[(i+1)//2]:
            resemble.append(i)
n = int(eval(input()))
ans = [0]*100000
q =[]
for i in range(1,100001):
    if i in resemble:
        ans[i-1] = ans[i-2] + 1
    elif i>1:
        ans[i-1] = ans[i-2]
for i in range(n):
    l,r = list(map(int,input().split()))
    if l>1:
        q.append(ans[r-1]-ans[l-2])
    elif r>1:
        q.append(ans[r-1])
    else:
        q.append(0)
for i in range(n):
    print((q[i]))

# Optimized solution
def prime_list(n):
    # n以下の自然数で素数か否かのリストを作成
    ans = [True for _ in range(n+1)]
    ans[0] = False
    ans[1] = False
    for i in range(2,n+1):
        if ans[i]:
            for j in range(2*i,n+1,i):
                ans[j] = False
    return ans

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

q = int(eval(input()))
for i in range(q):
    l,r = list(map(int,input().split()))
    print((like[r]-like[l-1]))
# Original solution
import math
q = int(eval(input()))
list_range = [list(map(int, input().split())) for _ in range(q)]

max_range = math.sqrt(10**5)
list_search = [i for i in range(2, 10**5 + 1)]
list_prime = []
while list_search[0] <= max_range:
  list_prime.append(list_search[0])
  temp = list_search[0]
  list_search = [i for i in list_search if i % temp != 0]
list_prime.extend(list_search)

list_satisfy = []
for one_prime in list_prime:
  if one_prime * 2 > 10**5:
    break
  if one_prime * 2 - 1 in list_prime:
    list_satisfy.append(one_prime * 2 - 1)

result = [0 for _ in range(q)]
for one_num in list_satisfy:
  for i in range(q):
    if list_range[i][0] <= one_num <= list_range[i][1]:
      result[i] += 1
for one_result in result:
  print(one_result)

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

list_flag_prime = [1 for i in range(10**5+1)]
list_flag_prime[0:2] = [0, 0]
for i in range(2, 10**5+1):
  if list_flag_prime[i] == 1:
    for j in range(2*i, 10**5+1, i):
      list_flag_prime[j] = 0

list_subj = [0 for i in range(10**5+1)]
for i in range(3, 10**5+1, 2):
  if list_flag_prime[i] == 1 & list_flag_prime[int((i+1)/2)] == 1:
    list_subj[i] += 1

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

for l, r in list_range:
  print((list_satisfy[r] - list_satisfy[l-1]))
# Original solution
def prime_table(n):
    arr = [True]*(n+1)
    arr[0], arr[1] = False, False
    for i in range(2, N+1):
        if not arr[i]: continue
        j = 2*i
        while j <= n:
            arr[j] = False
            j += i
    return arr
N = 10**5
pt = prime_table(N)
cum = [0]*(N+1)
for i in range(1, N+1, 2):
    if pt[i] and pt[(i+1)//2]:
        cum[i] = 1
for i in range(1, N+1):
    cum[i] += cum[i-1]
Q = int(input())
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(cum[r]-cum[l-1])
print(*ans, sep="\n")


# Optimized solution
def prime_table(n):
    prime = [True]*(n+1)
    prime[0], prime[1] = False, False
    i = 2
    while i*i <= n:
        if not prime[i]:
            i += 1
            continue
        j = 2*i
        while j <= n:
            prime[j] = False
            j += i
        i += 1
    return prime
N = 10**5
pt = prime_table(N)
cum = [0]*(N+1)
for i in range(1, N+1, 2):
    if pt[i] and pt[(i+1)//2]:
        cum[i] = 1
for i in range(1, N+1):
    cum[i] += cum[i-1]
Q = int(input())
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(cum[r]-cum[l-1])
print(*ans, sep="\n")
# Original solution
import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data

Q=int(eval(input()))
l=[]
r=[]
up=0
for i in range(Q):
    a,b=list(map(int,input().split()))
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=era(up)
like=[]

for i in range(len(s)):
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])
        
sumli=[0]*100001
tmp=0
for i in range(2,100001):
    if(i==like[tmp]):
        sumli[i]=sumli[i-1]+1
        if(tmp<(len(like)-1)):
            tmp+=1
    else:
        sumli[i]=sumli[i-1]

for i in range(Q):
    print((sumli[r[i]]-sumli[l[i]-1]))

# Optimized solution
import math
import bisect
def era(n):
    data=[i for i in range(2,n+1)]
    for d in data:
        data=[x for x in data if(x==d or x%d != 0)]
    return data
    
def prime(n):
    max=int(math.sqrt(n))
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=max:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes

Q=int(eval(input()))
l=[]
r=[]
up=0
for i in range(Q):
    a,b=list(map(int,input().split()))
    up=max([up,a,b])
    
    l.append(a)
    r.append(b)
s=prime(up)
like=[]

for i in range(len(s)):#O(10000*log(10000))
    if((s[i]+1)/2==s[bisect.bisect_left(s,(s[i]+1)/2)]):
        like.append(s[i])
        
sumli=[0]*100001
tmp=0
for i in range(2,100001):#O(100000)
    if(i==like[tmp]):
        sumli[i]=sumli[i-1]+1
        if(tmp<(len(like)-1)):
            tmp+=1
    else:
        sumli[i]=sumli[i-1]

for i in range(Q):
    print((sumli[r[i]]-sumli[l[i]-1]))
# Original solution
def eratosthenes(n):
    prime = [2]
    if n == 2:
        return prime
    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]


def solve():
    Q = int(eval(input()))
    primes = set(eratosthenes(10 ** 5))
    like_2017 = [0] * (10 ** 5 // 2)
    for i in range(3, 10 ** 5, 2):
        if i in primes and (i + 1) // 2 in primes:
            like_2017[i // 2] = like_2017[i // 2 - 1] + 1
        else:
            like_2017[i // 2] = like_2017[i // 2 - 1]
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        if l == 1:
            l = 2
        if r == 1:
            r = 2
        ans = like_2017[r // 2] - like_2017[l // 2 - 1]
        print(ans)


if __name__ == '__main__':
    solve()


# Optimized solution
def eratosthenes(n):
    prime = [2]
    if n == 2:
        return prime
    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]


def solve():
    Q = int(eval(input()))
    primes = set(eratosthenes(10 ** 5))
    like_2017 = [0] * (10 ** 5 // 2)
    for i in range(3, 10 ** 5, 2):
        if i in primes and (i + 1) // 2 in primes:
            like_2017[i // 2] = like_2017[i // 2 - 1] + 1
        else:
            like_2017[i // 2] = like_2017[i // 2 - 1]
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        ans = like_2017[r // 2] - like_2017[max(0, l // 2 - 1)]
        print(ans)


if __name__ == '__main__':
    solve()