CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
"""素因数分解"""
def factrize(n):
    b = 2
    while b*b <= n:
        if n % b == 0:
            return False
        b = b+1
    return True

f = [2]

for i in range(3,10**5+2,2):
    if factrize(i):
        f.append(i)

c = []

for j in f:
    if (j + 1)//2 in f:
        c.append(j)

o = []
res = 0
for k in range(10**5+1):
    if k in c:
        res += 1
    elif c == 2017:
        res += 1
    o.append(res)
    

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





# Optimized solution
import sys
import bisect
readline = sys.stdin.buffer.readline

"""素数判定はこっち"""
def factrize(n):
    b = 2
    while b*b <= n:
        if n % b == 0:
            return False
        b = b+1
    return True

f = []

for i in range(3,10**5+2,2):
    if factrize(i):
        if factrize((i+1)//2):
            f.append(i)
q = int(readline())
for _ in range(q):
    l,r = list(map(int,readline().split()))
    print((bisect.bisect(f,r)-bisect.bisect(f,l-1)))
# Original solution
#!/usr/bin/env python3
from itertools import accumulate
def erat(m):
    p = [1] * m
    p[0] = p[1] = 0
    for x in range(2, int((~-m)**.5) + 1):
        if p[x]:
            for y in range(x*x, m, x):
                p[y] = 0
    return p

INF = 10**5 + 1
p = erat(INF)
q = [0] * INF
for n in range(INF):
    q[n] = n%2 * p[n] * p[-~n//2]
*a, = accumulate([0] + q)
for _ in [None] * int(eval(input())):
    l, r = list(map(int, input().split()))
    print((a[r + 1] - a[l]))

# Optimized solution
def erat(M):
    p = [1] * M
    p[0] = p[1] = 0
    for x in range(2, int((M - 1)**.5) + 1):
        if p[x]:
            for y in range(x*x, M, x):
                p[y] = 0
    return p
INF = 10**5 + 1
p = erat(INF)
q = [0] * INF
from itertools import*
for i in range(INF):
    q[i] = i%2 * p[i] * p[-~i//2]
*a, = accumulate([0] + q)
for _ in [None] * int(eval(input())):
    l, r = list(map(int, input().split()))
    print((a[-~r] - a[l]))
# Original solution
def prime(i):
    if i == 2:
        return True
    else:
        if i % 2 == 0:
            return False
        for j in range(3, int(i**0.5)+1, 2):
            if i % j == 0:
                return False
        return True

Q = int(eval(input()))
l_r = [[int(_) for _ in input().split()] for _ in range(Q)]
Csum = [0]*(10**5+1)
cnt = 0

for i in range(3, 10**5, 2):
    if prime(i) and prime((i+1)//2):
        cnt += 1
    Csum[i] = cnt

for i in l_r:
    print((Csum[i[1]]-Csum[i[0]-2]))

# Optimized solution
Q = int(eval(input()))
l_r = [[int(_) for _ in input().split()] for _ in range(Q)]
prime = [False]*(10**5+1)
Csum = [0]*(10**5+1)

for i in range(2, 10**5+1):
    if not prime[i]:
        for j in range(i*2, 10**5+1, i):
            prime[j] = True

cnt = 0
for i in range(3, 10**5+1, 2):
    if (not prime[i]) and (not prime[(i+1)//2]):
        cnt += 1
    Csum[i] = cnt

for i in l_r:
    print((Csum[i[1]]-Csum[i[0]-2]))
# Original solution
import bisect

def Get_Sieve_of_Eratosthenes(N):
    prime_list = [2]
    limit = int(N ** 0.5)
    numeric_data = [i for i in range(3, N, 2)]
    while True:
        prime = numeric_data[0]
        if prime >= limit:
            return prime_list + numeric_data
        prime_list.append(prime)
        numeric_data = [x for x in numeric_data if x % prime != 0]

def Get_2017_like_number(N, prime_list):
    ans_list = []
    for p in prime_list:
        if (p+1)//2 in prime_list:
            ans_list.append(p)
    return ans_list


def main():
    N = 10 ** 5
    prime_list = Get_Sieve_of_Eratosthenes(N)
    like_number_list = Get_2017_like_number(N, prime_list)

    # 入力
    Q = int(eval(input()))
    Query = [list(map(int, input().split())) for _ in range(Q)]
    
    for q in Query:
        l = q[0]
        r = q[1]
        print((bisect.bisect_right(like_number_list, r) - bisect.bisect_left(like_number_list, l)))


if __name__ == "__main__":
    main()

# Optimized solution
N = 10**5
prime_list = [True] * (N+1)        # True が素数
count_list = [0] * (N+1)
for i in range(2, N+1, 1):
    if prime_list[i]:
        for j in range(i+i, N+1, i):
            prime_list[j] = False

for i in range(3, N+1, 2):
    if prime_list[i] and prime_list[(i+1)//2]:
        count_list[i] += 1

for i in range(3, N+1, 1):
    count_list[i] += count_list[i-1]

Q = int(eval(input()))
query = [list(map(int, input().split())) for _ in range(Q)]
for q in query:
    l, r = q
    print((count_list[r] - count_list[l-1]))
# Original solution
def is_prime(num):
    if num == 1:
        return False
    limit = int(num ** 0.5) + 1
    for i in range(2, limit):
        if num % i == 0:
            return False
    return True


cumsum = [0] * (10**5 + 2)

count = 0
for num in range(1, 10**5, 2):
    if is_prime(num):
        if is_prime((num+1)//2):
            count += 1

    cumsum[num] = count
    cumsum[num+1] = count

q = int(eval(input()))
for i in range(q):
    left, right = list(map(int, input().split()))
    res = cumsum[right] - cumsum[left-1]
    print(res)

# Optimized solution
primes = set(range(3, 10**5, 2))
primes.add(2)
cumsum = [0] * (10**5 + 2)

for i in range(3, 10**5):
    if i in primes:
        for not_prime in range(i+i, 10**5, i):
            primes.discard(not_prime)


count = 0
for num in range(1, 10**5, 2):
    if num in primes:
        if (num+1)//2 in primes:
            count += 1

    cumsum[num] = count
    cumsum[num+1] = count

q = int(eval(input()))
for i in range(q):
    left, right = list(map(int, input().split()))
    res = cumsum[right] - cumsum[left-1]
    print(res)
# Original solution
#!/usr/bin/env python3

def main():
    is_prime = sieve(10 ** 5 + 1)
    is_like2017 = [(is_prime[i] and is_prime[(i + 1) // 2]) for i in range(10 ** 5 + 1)]
    counter = [0]
    for i in range(1, 10 ** 5 + 1):
        counter.append(counter[-1] + (1 if is_like2017[i] else 0))

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


# O(nloglogn) https://mathtrain.jp/eratosthenes
def sieve(n):  # exclusive
    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

if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3

import sys

def main():
    is_prime = sieve(10 ** 5 + 1)
    is_like2017 = [(is_prime[i] and is_prime[(i + 1) // 2]) for i in range(10 ** 5 + 1)]
    counter = [0]
    for i in range(1, 10 ** 5 + 1):
        counter.append(counter[-1] + (1 if is_like2017[i] else 0))

    q = int(eval(input()))
    for i in range(q):
        l, r = list(map(int, sys.stdin.readline().split()))
        print((counter[r] - counter[l - 1]))


# O(nloglogn) https://mathtrain.jp/eratosthenes
def sieve(n):  # exclusive
    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

if __name__ == "__main__":
    main()
# Original solution
import math
Q = int(eval(input()))

ps = []
maxfac = math.sqrt(10**5)
nums = [i+1 for i in range(1, 10**5)]
while True:
    p = nums[0]
    if maxfac <= p:
        break
    ps.append(p) 
    nums = [num for num in nums if num % p != 0]

ps = set(ps + nums)

c = [0] * 10**5
for i in range(3, 10**5+1, 2):
    if i in ps and (i+1)//2 in ps:
        c[i] = 1

from itertools import accumulate
cs = list(accumulate(c))

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

# Optimized solution
Q = int(eval(input()))
maxn = 10**5
is_prime = [True if i%2 == 1 else False for i in range(0, maxn+1) ]
is_prime[0] = False
is_prime[1] = False
is_prime[2] = True
for i in range(3, int(maxn**0.5) + 1, 2):
    if not is_prime[i]:
        continue
    for j in range(i*2, maxn+1, i):
        is_prime[j] = False

ps = [i for i in range(maxn+1) if is_prime[i]]
ps = set(ps)

c = [0] * 10**5
for i in range(3, 10**5+1, 2):
    if i in ps and (i+1)//2 in ps:
        c[i] = 1

from itertools import accumulate
cs = list(accumulate(c))

for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l-1]))
# Original solution
def isPrime(n):
    for p in primes:
        if n%p == 0:
            return False
        elif n < p*p:
            return True

primes = [2,3,5,7]
for i in range(11,10**5,2):
    if isPrime(i):
        primes.append(i)
n2017s = [0]
for p in primes[1:]:
    if (p+1)//2 in primes:
        n2017s.append(p)

def binary_search(n):
    l=0
    r=len(n2017s)-1
    while l+1<r:
        i = (l+r)//2
        if n2017s[i] > n:
            r = i
        else:
            l = i
    return l

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

# Optimized solution
def isPrime(n):
    for p in primes:
        if n%p == 0:
            return False
        elif n < p*p:
            return True

primes = [2,3,5,7]
for i in range(11,10**5,2):
    if isPrime(i):
        primes.append(i)
n2017s = [0]
for p in primes[1:]:
    if (p+1)//2 in primes:
        n2017s.append(p)
n2017s.append(10**6)
        
def binary_search(n):
    l=0
    r=len(n2017s)-1
    while l+1<r:
        i = (l+r)//2
        if n2017s[i] > n:
            r = i
        else:
            l = i
    return l

Q = int(eval(input()))
for i in range(Q):
    l,r = list(map(int,input().split()))
    print((binary_search(r+1)-binary_search(l-1)))
# Original solution
Q = int(eval(input()))
LR = [list(map(int,input().split())) for _ in [0]*Q]

N = max(r for l,r in LR)

p = set()
for i in range(3,N+1,2):
    for j in p:
        if i%j==0:break
    else:
        p.add(i)
p.add(2)

c = [0]*(N+1)
for i in p:
    if (i+1)//2 in p:c[i] = 1

#累積和
class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

Sc = cumulative_sum(c)

for l,r in LR:
    print((Sc.get(l,r+1)))

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

N = max(r for l,r in LR)

p = []
for i in range(3,N+1,2):
    for j in p:
        if i%j==0: break
        if j*j>i:
            p.append(i)
            break
    else:
        p.append(i)
p.append(2)
p = set(p)

c = [0]*(N+1)
for i in p:
    if (i+1)//2 in p:c[i] = 1

class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

Sc = cumulative_sum(c)

for l,r in LR:
    print((Sc.get(l,r+1)))
# Original solution

Q = int(eval(input()))
N = 10**5 + 1000

def getPrimes():
    isPrime = [True] * N
    isPrime[1] = False
    for i in range(2, N):
        if not isPrime[i]:
            continue
        for p in range(i + i, N, i):
            isPrime[p] = False
    return isPrime

isPrime = getPrimes()

A = [0] * (N)
for i in range(2, N):
    if i % 2 == 1 and isPrime[i] and isPrime[(i + 1) // 2]:
        A[i] = 1
accA = [0] * (N + 1)
for i, a in enumerate(A, start=0):
    accA[i] += accA[i - 1] + a

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



# Optimized solution
Q = int(eval(input()))
R = 10**5 + 100

def getPrimes():
    isPrime = [True] * R
    isPrime[0] = False
    isPrime[1] = False
    for i in range(R):
        if not isPrime[i]:
            continue
        for p in range(i * 2, R, i):
            isPrime[p] = False
    return isPrime

isPrime = getPrimes()
A = [1 if i % 2 == 1 and isPrime[i] and isPrime[(i + 1) // 2] else 0 for i in range(R)]
accA = [0] * R
for i in range(1, R):
    accA[i] = accA[i - 1] + A[i - 1]
accA = accA[1:]

for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((accA[r] - accA[l - 1]))
# Original solution
def isprime(n):
    '''check if integer n is a prime'''

    # make sure n is a positive integer
    n = abs(int(n))

    # 0 and 1 are not primes
    if n < 2:
        return False

    # 2 is the only even prime number
    if n == 2:
        return True

    # all other even numbers are not primes
    if not n & 1:
        return False

    # range starts with 3 and only needs to go up
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False

    return True

def resolve():
	q = int(eval(input()))
	qs = [list(map(int, input().split())) for _ in range(q)]
	t = [0]*(10**5+1)
	for i in range(10**5):
		v = 1 if isprime(i+1) and isprime((i+2)/2) else 0
		t[i+1] = t[i] + v
	for l, r in qs:
		if l == r:
			print((1 if isprime(l) and isprime((l+2)/2) else 0))
		else:
			print((t[r] - t[l-1]))
resolve()

# Optimized solution
def sieve(n):
	is_prime = [1] * (n + 1)
	is_prime[0], is_prime[1] = 0, 0
	for i in range(2, n+1):
		if not is_prime[i]:
			continue
		j = i*2
		while j <= n:
			is_prime[j] = 0
			j += i
	return is_prime

def resolve():
	q = int(eval(input()))
	qs = [list(map(int, input().split())) for _ in range(q)]
	ps = sieve(10**5)
	seq = [0] * (10**5+1)
	for i in range(len(ps)-1, 1, -1):
		if ps[i] and ps[(i+1)//2]:
			continue
		ps[i] = 0
	for i in range(1, 10**5):
		seq[i+1] = seq[i] + ps[i+1]
	for l, r in qs:
		if l == r:
			print((ps[l]))
		else:
			print((seq[r] - seq[l-1]))
resolve()
# Original solution
Q = int(eval(input()))
numberlist = [0 for i in range(100001)]
prime = [2]

for i in range(3, 100001, 2):
    flag = 1
    for j in prime:
        if i % j == 0:
            flag = 0
            break
    if flag == 1:
        prime.append(i)

for i in prime:
    if (i+1)//2 in prime:
        numberlist[i] += 1
for i in range(100000):
    numberlist[i+1] += numberlist[i]


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


# Optimized solution
import sys
input = sys.stdin.readline
Q = int(eval(input()))
numberlist = [0 for i in range(100001)]
prime = [2]

for i in range(3, 100001, 2):
    flag = 1
    for j in prime:
        if i % j == 0:
            flag = 0
            break
    if flag == 1:
        prime.append(i)

for i in prime:
    if (i+1)//2 in prime:
        numberlist[i] += 1
for i in range(100000):
    numberlist[i+1] += numberlist[i]


for i in range(Q):
    l, r = list(map(int, input().split()))
    print((numberlist[r]-numberlist[l-1]))
# Original solution
q = int(eval(input()))
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


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


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

like_2017 = []
count = [0 for _ in range(10 ** 5)]
for i in range(len(primes)):
    if primes[i] * 2 - 1 in primes:
        like = 2 * primes[i] - 1
        count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print((count[lr[i][1]] - count[lr[i][0] - 1]))


# Optimized solution
q = int(eval(input()))
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


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


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

like_2017 = []
count = [0 for _ in range(10 ** 5)]
for i in range(len(primes)):
    if binarySearch(primes, primes[i] * 2 - 1):
        like = 2 * primes[i] - 1
        count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print((count[lr[i][1]] - count[lr[i][0] - 1]))
# Original solution
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from time import time

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

def main():
    q = int(input().strip())
    n = 10**5
    ary = [0] * (n+1)
    ary2 = [0] * (n+1)
    arys = [0] * (n+2)
    for i in range(2, n+1):
        ary[i] = is_prime(i)
    for i in range(1, n+1):
        ary2[i] = ary[i] & is_prime((i+1)//2)
    for i in range(1, n+2):
        arys[i] = arys[i-1] + ary2[i-1]
    # print(ary[:20])
    # print(ary2[:20])
    # print(arys[:20])
    for i in range(q):
        l, r = list(map(int, input().strip().split()))
        print((arys[r+1] - arys[l]))

if __name__ == '__main__':
    main()


# Optimized solution
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from time import time

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

def main():
    q = int(input().strip())
    n = 10**5
    ary = [0] * (n+1)
    ary2 = [0] * (n+1)
    arys = [0] * (n+2)
    for i in range(2, n+1):
        ary[i] = is_prime(i)
    for i in range(1, n+1):
        ary2[i] = ary[i] & ary[(i+1)//2]
    for i in range(1, n+2):
        arys[i] = arys[i-1] + ary2[i-1]
    # print(ary[:20])
    # print(ary2[:20])
    # print(arys[:20])
    for i in range(q):
        l, r = list(map(int, input().strip().split()))
        print((arys[r+1] - arys[l]))

if __name__ == '__main__':
    main()
# Original solution
Q=int(eval(input()))
def make_divisors(n):
    divisors = []
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)

    return divisors
l=[]
r=[]
for i in range(Q):
    a,b=list(map(int,input().split()))
    l.append(a)
    r.append(b)
ml=[]
c=[0 for i in range(10**5+1)]
for i in range(1,10**5+1,2):
    ml=make_divisors(i)
    if len(ml)==2:
        n=make_divisors((i+1)//2)
        if len(n)==2:
            c[i]=1
#print(c)
ans=[]
for i in range(Q):
    ad=sum(c[l[i]:r[i]+1])
    ans.append(ad)
    print((ans[i]))

# Optimized solution
M=10**6
p=[1]*M
p[0]=p[1]=0
for i in range(2,4*10**4):
    if p[i]:
        for j in range(i*i,M,i):
            p[j]=0
C=[0]*M
for i in range(2,M):
    if p[i] and p[(i+1)//2]:
        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
from itertools import accumulate
def sosuu(n):
  if n==1:
    return False
  else:
    for i in range(2,int(math.sqrt(n)+1)):
      if n%i==0:
        return False
    return True

#入力
q=int(eval(input()))
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=list(map(int,input().split()))
L=min(l)
R=max(r)

#累積和を作る
A=[]
for i in range(L,R+1):
  if i%2==0:
    A.append(0)
  else:
    if sosuu(i) and sosuu(int((i+1)/2)):
      A.append(1)
    else:
      A.append(0)
s=[0]+A
S=list(accumulate(s))
for i in range(q):
    #print(S[r[i]-L+1])
    #print(S[l[i]-L])
    print((S[r[i]-L+1]-S[l[i]-L]))
    



# Optimized solution
import math
from itertools import accumulate
q=int(eval(input()))
l=[]
r=[]
for i in range(q):
  a,b=list(map(int,input().split()))
  l.append(a)
  r.append(b)
  
def is_prime(n):
  if n==1:
    return False
  elif n==2:
    return True
  else:
    for i in range(2,int(math.sqrt(n)+1)):
      if n%i==0:
        return False
  return True

l_min=min(l)
r_max=max(r)
ruiseki=[]
for i in range(l_min,r_max+1):
  if i%2==1 and is_prime(i) and is_prime((i+1)//2):
    ruiseki.append(1)
  else:
    ruiseki.append(0)
    
ruiseki=[0]+list(accumulate(ruiseki))

for i in range(q):
  print((ruiseki[r[i]-l_min+1]-ruiseki[l[i]-l_min]))
# Original solution
import math

Q = int(eval(input()))

# 素数表
n = 100000
P = [False] * n
P[2] = True
for i in range(3, n, 2):
    k = True
    for j in range(3, int(math.sqrt(i)) + 1, 2):
        if i % j == 0:
            k = False
            break
    if k:
        P[i] = True

# Nと(N+1)÷2が素数か否か
a = [0] * n
for i in range(1, n, 2):
    j = (i + 1) // 2
    if P[i] and P[j]:
        a[i] = 1
# 累積和
for i in range(n - 1):
    a[i + 1] += a[i]

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


# Optimized solution
import sys
from itertools import accumulate

input = sys.stdin.readline

N = int(eval(input()))


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


primes = prime_boolean_table(10**5)
A = [0] * 10**5
for i in range(1, 10**5):
    A[i] += A[i - 1]
    if primes[i] and primes[(i + 1) // 2]:
        A[i] += 1

for _ in range(N):
    l, r = list(map(int, input().split()))
    print((A[r] - A[l - 1]))
# Original solution
from sys import stdin
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
prime_list=[i for i in range(2,100000) if is_prime(i)]
oppai=[0]*100000
oppai[1]=0
before=1
for num in prime_list:
    if (num+1)//2 in prime_list:
        oppai[before:num - 2] = [oppai[before]] * (num-1 - before)
        oppai[num-1]=oppai[before]+1
    else:oppai[before:num-1]=[oppai[before]]*(num-before)
    before=num-1
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=list(map(int,(input().split())))
    if a==b:
        bb = (oppai[b - 1])
        aa = (oppai[a - 2])
        count = bb - aa
        print(count)
    else:
        if a>=2:
            bb = oppai[b - 1]
            aa = oppai[a - 2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)





# Optimized solution
from sys import stdin
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
prime_list=[i for i in range(2,100000) if is_prime(i)]
oppai=[0]*100000
oppai[1]=0
before=1
for num in prime_list:
    if (num+1)//2 in prime_list:
        oppai[before:num - 2] = [oppai[before]] * (num-1 - before)
        oppai[num-1]=oppai[before]+1
    else:oppai[before:num-1]=[oppai[before]]*(num-before)
    before=num-1
oppai[99991:99999]=[oppai[99990]]*8
N=list(map(int,stdin.readline().strip().split()))[0]
for _ in range(N):
    count = 0
    a,b=list(map(int,stdin.readline().strip().split()))
    if a==b:
        bb = (oppai[b - 1])
        aa = (oppai[a - 2])
        count = bb - aa
        print(count)
    else:
        if a>=2:
            bb = oppai[b - 1]
            aa = oppai[a - 2]
            count = bb - aa
            print(count)
        else:
            bb = oppai[b - 1]
            count = bb
            print(count)