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

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

plist=[False]*(10**5+3)
for i in range(3,10**5+3,2):
  if isPrime(i) and isPrime((i+1)//2):
    plist[i]=True
#print(plist[:10])

slist=[0]*(10**5+3)
for i in range(3,10**5+3):
  if plist[i]:
    slist[i]=slist[i-1]+1
  else:
    slist[i]=slist[i-1]
#print(slist[:10])
  
for i in range(Q):
  l,r=list(map(int,input().split()))
  print((slist[r]-slist[l-1]))

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

def prime_sieve(n):
  prime_list=[True]*n
  prime_list[0]=False
  prime_list[1]=False
  for i in range(2,int(n**0.5)+1):
    if not prime_list[i]:
      continue
    else:
      for j in range(i**2,n,i):
        prime_list[j]=False
  
  return prime_list
  #return [i for i in range(n) if is_prime_list[i]]

prime_list=prime_sieve(10**5+1)
#print(prime_list[:10])
  
plist=[0]*(10**5+1)
for i in range(3,10**5+1,2):
  if prime_list[i] and prime_list[(i+1)//2]:
    plist[i]=1
#print(plist[:10])

slist=[0]*(10**5+1)
for i in range(3,10**5+1):
  slist[i]=plist[i]+slist[i-1]
#print(slist[:10])
  
for i in range(Q):
  l,r=list(map(int,input().split()))
  print((slist[r]-slist[l-1]))
# Original solution
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    #table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime
n=10**5+2
a=sieve(n)
ans=[0]*(n//2)
for i in range(0,n,2):
    if a[i] and a[i//2]:
        ans[i//2]=1
#print(ans[:20])
for i in range(1,n//2):
    ans[i]+=ans[i-1]
#print(ans[:20])
q=int(eval(input()))
for i in range(q):
    l,r=list(map(int,input().split()))
    if l==1:
        l=2
    if r==1:
        r=2
    print((ans[r//2]-ans[l//2 -1]))

# Optimized solution
import sys
input = sys.stdin.readline
from math import sqrt


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    # return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]
    # x が素数か判定したいとき
    return {2, 3}.union({3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]})


sieve = Eratosthenes(10 ** 5 + 1)
ans = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    if i in sieve and (i + 1) // 2 in sieve:
        ans[i] += 1
for i in range(3, 10 ** 5):
    ans[i + 1] += ans[i]
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((ans[r] - ans[l - 1]))
# Original solution
import sys
input = sys.stdin.readline
from math import sqrt


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    # return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]
    # x が素数か判定したいとき
    return {2, 3}.union({3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]})


sieve = Eratosthenes(10 ** 5 + 1)
ans = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    if i in sieve and (i + 1) // 2 in sieve:
        ans[i] += 1
for i in range(3, 10 ** 5):
    ans[i + 1] += ans[i]
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((ans[r] - ans[l - 1]))


# Optimized solution
import sys
input = sys.stdin.readline
from math import sqrt


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    s = [False] * n
    for i in range(1, n // 3 - correction):
        if sieve[i]:
            s[3 * i + 1 | 1] = True
    s[2] = True
    s[3] = True
    return s


sieve = Eratosthenes(10 ** 5 + 1)
ans = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    if sieve[i] and sieve[(i + 1) // 2]:
        ans[i] += 1
for i in range(3, 10 ** 5):
    ans[i + 1] += ans[i]
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((ans[r] - ans[l - 1]))
# Original solution
import math
RMAX = 10**5

def get_primes(n):
    ps = []
    upper = math.sqrt(n)
    data = [i+1 for i in range(1, n)]
    while True:
        p = data[0]
        if p >= upper:
            break
        ps.append(p)
        data = [e for e in data if e%p != 0]
    return ps + data

primes = get_primes(RMAX)
primes_set = set(primes)
sim_2017 = [0]*(RMAX+1)
for p in primes:
    if (p+1)//2 in primes_set:
        sim_2017[p] = 1

for i in range(1, len(sim_2017)):
    sim_2017[i] += sim_2017[i-1]

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


# Optimized solution
NMAX = 10**5+1

is_prime = [True]*NMAX
for i in range(2, NMAX):
    if is_prime[i]:
        for j in range(2*i, NMAX, i):
            is_prime[j] = False

sim_2017 = [0]*NMAX
for i in range(3, NMAX, 2):
    if is_prime[i] and is_prime[(i+1)//2]:
        sim_2017[i] += 1
for i in range(1, NMAX):
    sim_2017[i] += sim_2017[i-1]

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

# def primes(x):
#     if x < 2: return []

#     primes = [i for i in range(x)]
#     primes[1] = 0 # 1は素数ではない
#     x_sqrt = math.sqrt(x) # 記憶させていちいち計算しない

#     # エラトステネスのふるい
#     for prime in primes:
#         if prime == 0:
#             continue # 先に処理
#         if prime > x_sqrt: 
#             break
#         for non_prime in range(2 * prime, x, prime):
#             primes[non_prime] = 0

#     return [prime for prime in primes if prime != 0]
def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False
                
q = int(eval(input()))
l_list = []
r_list = []
for _ in range(q):
    l, r = list(map(int,input().split()))
    l_list.append(l)
    r_list.append(r)
    
maxr = max(r_list)
p_list = list(primes_sieve2(maxr+1))

sim_list = []
for p in p_list:
    if (p+1)/2 in p_list:
        sim_list.append(p)
        
cumulation = [0 for _ in range(maxr+1)]
for s in sim_list:
    cumulation[s] = 1

for i in range(1,len(cumulation)):
    cumulation[i] += cumulation[i-1]

for i in range(q):
    print((cumulation[r_list[i]]-cumulation[l_list[i]-1]))

# Optimized solution
# -*- coding: utf-8 -*-
import math
Q = int(eval(input()))

ls = []
rs = []
for n in range(Q):
    l, r = list(map(int, input().split()))
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes


def count_similar(era, n):
    count_similar = [0 for i in range(n+1)]
    for i in range(1,n+1):
        count_similar[i] = count_similar[i-1]
        if era[i] == 1 and era[int((i+1)/2)] == 1:
            count_similar[i] += 1
    return count_similar




era = eratos(max_r)
cnt = count_similar(era, max_r)

for l, r in zip(ls, rs):
    print((cnt[r] - cnt[l-1]))
# Original solution
n=8**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
for i in range(1,n):S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(eval(input())):l,r=list(map(int,input().split()));print((S[r]-S[l-1]))

# Optimized solution
n=7**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
for i in range(1,n):S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(eval(input())):l,r=list(map(int,input().split()));print((S[r]-S[l-1]))
# Original solution
n=7**6;P=[0,0]+[1]*n;S=[0]*n;r=list(range(2,n))
for i in r:
  for j in range(2*i,n,i):P[j]=0
for i in r:S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(eval(input())):l,r=list(map(int,input().split()));print((S[r]-S[l-1]))

# Optimized solution
n=7**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
  S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(eval(input())):l,r=list(map(int,input().split()));print((S[r]-S[l-1]))
# Original solution
import sys
import math
def input(): return sys.stdin.readline().rstrip()

def isPrime(n):
    if n <= 2:
        return 0

    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    else:
        return 1

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

    MAX = 10 ** 5
    prime = [0] * MAX
    for i in range(1, MAX):
        prime[i] = prime[i-1] + isPrime(i)
    for i in lr:
        l, r = i
        if prime[l] != prime[l-1]:
            print((prime[r] - prime[l]+1))
        else:
            print((prime[r] - prime[l]))
if __name__ == '__main__':
    main()

# Optimized solution
import sys
import math
def input(): return sys.stdin.readline().rstrip()

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    else:
        return 1

def main():
    Q = int(eval(input()))

    MAX = 10 ** 5
    prime = [0] * MAX
    for i in range(3, MAX):
        prime[i] = prime[i-1] + isPrime(i)

    for _ in range(Q):
        l, r = list(map(int, input().split()))
        print((prime[r] - prime[l-1]))
if __name__ == '__main__':
    main()
# Original solution
import sys
import math
def input(): return sys.stdin.readline().rstrip()

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    else:
        return 1

def main():
    Q = int(eval(input()))

    MAX = 10 ** 5
    prime = [0] * MAX
    for i in range(3, MAX):
        prime[i] = prime[i-1] + isPrime(i)

    for _ in range(Q):
        l, r = list(map(int, input().split()))
        print((prime[r] - prime[l-1]))
if __name__ == '__main__':
    main()

# Optimized solution
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = [0] * (MAX + 1)
    sum = 0
    prime = set()
    memo = [False] * 2 + [True] * (MAX - 1)
    for i in range(2, MAX + 1):
        if memo[i]:
            prime.add(i)
            for j in range(i * 2, MAX + 1, i):
                memo[j] = False
            if (i + 1) // 2 in prime:
                sum += 1
        ans[i] = sum
    
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        print((ans[r] - ans[l-1]))

if __name__ == '__main__':
    main()
# Original solution
from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)
# print(max_n)
# print(l_r)

a = [i for i in range(max_n+1)]

def isPrime(num):
    if num == 0 or num == 1:
        return False
    ans = True
    for i in range(2,int(num/2)+1):
        if num % i == 0:
            ans = False
            break
    return ans

b = [1 if isPrime(x) else 0 for x in a]
# print(b)
c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 
# print(c)
s = list(accumulate(c))
# print(len(s))

for i in range(q):
    print((s[l_r[i][1]]-s[l_r[i][0]-1]))

# Optimized solution
from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)
# print(max_n)
# print(l_r)

a = [i for i in range(max_n+1)]

def isPrime(num):
    if num == 0 or num == 1:
        return False
    ans = True
    for i in range(2,int(num/2)+1):
        if num % i == 0:
            ans = False
            break
    return ans
b = [1] * (max_n+1)
b[0] = 0
b[1] = 0
for i in range(2,max_n+1):
    if b[i]:
        j = i*2
        while j <= max_n:
            b[j] = 0
            j += i
# print(b)
c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 
# print(c)
s = list(accumulate(c))
# print(len(s))

for i in range(q):
    print((s[l_r[i][1]]-s[l_r[i][0]-1]))
# Original solution
import bisect

q = int(eval(input()))

def pr(n):
    is_prime = [True]*(n+2)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int((n+1)**0.5)+1):
        for j in range(2,i+1):
            if is_prime[i] == False:
                continue
            for k in range(2*i,n+1,i):
                is_prime[k] = False
                
    return is_prime
    
L = pr(10**5*2+2000)

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

for i in range(q):
    l,r = list(map(int,input().split()))
    l_ = bisect.bisect_left(li,l)
    r_ = bisect.bisect_right(li,r)
    print((r_ - l_))


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

def pr(n):
    L = [1]*(n+1)
    L[0] = 0
    L[1] = 0
    for i in range(2,n+1):
        for j in range(2*i,n,i):
            L[j] = 0
    return L
    
a = pr(100001)

li = [0]*(100001)
for i in range(1,100000,2):
    if a[i] and a[(i+1)//2]:
        li[i] = 1
        
from itertools import accumulate
b = list(accumulate(li))

for i in range(q):
    l,r = list(map(int,input().split()))
    print((b[r]-b[l-1]))
# Original solution
import math
N = 10**5

Q = int(eval(input()))


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


primes = eratosthenes(N)

like_2017 = [False] * (10**5 + 1)

for p in primes:
    if (p + 1) // 2 in primes:
        like_2017[p] = True


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


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


# Optimized solution
import math
N = 10**5

Q = int(eval(input()))


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


_primes = eratosthenes(N)

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

for p in _primes:
    primes[p] = True

like_2017 = [False] * (10**5 + 1)

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


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


for _ in range(Q):
    left, right = list(map(int, input().split()))
    print((C[right] - C[left - 1]))
# Original solution
# -*- coding: utf-8 -*-
import math
Q = int(eval(input()))

ls = []
rs = []
for n in range(Q):
    l, r = list(map(int, input().split()))
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes


def count_similar(era, n):
    is_similar = [0 for i in range(n+1)]
    for i in range(n+1):
        if era[i] == 1 and era[int((i+1)/2)] == 1:
            is_similar[i] = 1
    count_similar = [0 for i in range(n+1)]
    for i in range(n+1):
        count_similar[i] = sum(is_similar[0:i+1])
    return count_similar




era = eratos(max_r)
cnt = count_similar(era, max_r)

for l, r in zip(ls, rs):
    print((cnt[r] - cnt[l-1]))



# Optimized solution
# -*- coding: utf-8 -*-
import math
Q = int(eval(input()))

ls = []
rs = []
for n in range(Q):
    l, r = list(map(int, input().split()))
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes


def count_similar(era, n):
    count_similar = [0 for i in range(n+1)]
    for i in range(1,n+1):
        count_similar[i] = count_similar[i-1]
        if era[i] == 1 and era[int((i+1)/2)] == 1:
            count_similar[i] += 1
    return count_similar




era = eratos(max_r)
cnt = count_similar(era, max_r)

for l, r in zip(ls, rs):
    print((cnt[r] - cnt[l-1]))
# Original solution
import math
import copy

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def realprimes(y):
    Y = primes(y)
    t = int((y + 1) / 2)
    bestprime = []

    for prime in Y:
        if prime != 2:
            prime2 = (prime + 1)//2
            pw = 0
            for i in range(2,int(math.sqrt(prime2)) + 2):
                if prime2 == 2:
                    break
                elif prime2 % i == 0:
                    pw = 1
                    break
            if pw == 0:
                bestprime.append(prime)

    T = bestprime
    V = set(Y) & set(T)
    return list(V)
W = realprimes(10**5 - 1)
W.sort()

q = int(eval(input()))
s = []
for i in range(q):#h:高さ
    s.append([int(m) for m in input().split()])

ALL = [i + 1 for i in range(10**5)]
ALL2 = copy.deepcopy(ALL)

for i in range(q):
    ALL = ALL2[s[i][0] - 1:s[i][1]]
    length = len(set(ALL) & set(W))
    print(length)
    ALL = ALL2

# Optimized solution
import math
import copy

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

def realprimes(y):
    Y = primes(y)
    t = int((y + 1) / 2)
    bestprime = []

    for prime in Y:
        if prime != 2:
            prime2 = (prime + 1)//2
            pw = 0
            for i in range(2,int(math.sqrt(prime2)) + 2):
                if prime2 == 2:
                    break
                elif prime2 % i == 0:
                    pw = 1
                    break
            if pw == 0:
                bestprime.append(prime)

    T = bestprime
    V = set(Y) & set(T)
    return list(V)
W = realprimes(10**5 - 1)
W.sort()
W.append(10**5)
q = int(eval(input()))
s = []
for i in range(q):#h:高さ
    s.append([int(m) for m in input().split()])

j = 0
Z = []
for i in range(10 ** 5):
    if i < W[j]:
        Z.append(j)
    else:
        j += 1
        Z.append(j)

for i in range(q):
    if Z[s[i][0]] != Z[s[i][0] - 1]:
        print((Z[s[i][1]] - Z[s[i][0]] + 1))
    else:
        print((Z[s[i][1]] - Z[s[i][0]]))
# Original solution
import sys
input = sys.stdin.readline

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

q = int(eval(input()))
pl = primes(10**5)
ql = [p*2-1 for p in pl if p*2-1 in pl and p*2-1<=10**5+1]
for _ in range(q):
  l,r = list(map(int,input().split()))
  fil = list([x for x in ql if l<=x<=r])
  print((len(fil)))

# Optimized solution
import itertools

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

pl = prime_boolean_table(10**5)
ql = [0]*(10**5+1)
for i in range(1,10**5+1):
    if pl[i] and pl[(i+1)//2]:
        ql[i] += 1
ql = list(itertools.accumulate(ql))
q = int(eval(input()))
for _ in range(q):
    l,r = list(map(int,input().split()))
    print((ql[r]-ql[l-1]))
# Original solution
import itertools

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

pl = prime_boolean_table(10**5)
ql = [0]*(10**5+1)
for i in range(1,10**5+1):
    if pl[i] and pl[(i+1)//2]:
        ql[i] += 1
ql = list(itertools.accumulate(ql))
q = int(eval(input()))
for _ in range(q):
    l,r = list(map(int,input().split()))
    print((ql[r]-ql[l-1]))


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

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

def main():
    pl = prime_boolean_table(10**5)
    ql = [0]*(10**5+1)
    for i in range(1,10**5+1):
        if pl[i] and pl[(i+1)//2]:
            ql[i] += 1
    ql = list(itertools.accumulate(ql))
    q = int(eval(input()))
    for _ in range(q):
        l,r = list(map(int,input().split()))
        print((ql[r]-ql[l-1]))

if __name__=='__main__':
    main()