CodeEff/ECCO huggingface dataset:
# Original solution
import math

q = int(eval(input()))
cnt = [0] * (5 * 10 ** 4)
cnt[1] = 1
cnt[2] = 2


def is_prime(n):
    visit = []
    if n % 2 == 0:
        return 0
    for i in range(3, 1 + math.ceil(n ** (0.5))):
        if i not in visit:
            if n % i == 0:
                return 0
            else:
                visit.append(i)
    return 1


for i in range(3, 5 * 10 ** 4):
    odd = 2 * i + 1
    if odd % 3 != 1:
        cnt[i] = cnt[i - 1]
    else:
        k = 0
        if is_prime(odd) and is_prime((odd + 1) // 2):
            k = 1
            # print(odd, is_prime(odd), is_prime((odd + 1) // 2))
        cnt[i] = cnt[i - 1] + k
cnt.append(0)
for i in range(q):
    l, r = list(map(int, input().split()))
    print((cnt[(r - 1) // 2] - cnt[(l - 3) // 2]))


# Optimized solution
import math

q = int(eval(input()))
cnt = [0] * (5 * 10 ** 4)
cnt[1] = 1
cnt[2] = 2


def is_prime(n):
    visit = []
    if n % 2 == 0:
        return 0
    for i in range(3, 1 + math.ceil(n ** (0.5))):
        if i not in visit:
            if n % i == 0:
                return 0
            else:
                visit.append(i)
    return 1


for i in range(3, 5 * 10 ** 4):
    odd = 2 * i + 1
    if odd % 3 != 1 or (odd + 1) % 4 == 0:
        cnt[i] = cnt[i - 1]
    else:
        k = 0
        if is_prime(odd) and is_prime((odd + 1) // 2):
            k = 1
            # print(odd, is_prime(odd), is_prime((odd + 1) // 2))
        cnt[i] = cnt[i - 1] + k
cnt.append(0)
for i in range(q):
    l, r = list(map(int, input().split()))
    print((cnt[(r - 1) // 2] - cnt[(l - 3) // 2]))
# Original solution
Q = int(eval(input()))
l, r = [], []
for i in range(Q):
    _l, _r = list(map(int, input().split()))
    l.append(_l)
    r.append(_r)
max_r = max(r)
sosu = set()

for i in range(2, max_r+1):
    for s in sosu:
        if i%s == 0:
            break
    else:
        sosu.add(i)
sums = [0] * (max_r + 1)
for i in range(1, max_r+1):
    if i in sosu and (i+1)//2 in sosu:
        sums[i] = sums[i-1] + 1
    else:
        sums[i] = sums[i-1]

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



# Optimized solution
Q = int(eval(input()))
l, r = [], []
for i in range(Q):
    _l, _r = list(map(int, input().split()))
    l.append(_l)
    r.append(_r)
max_r = max(r)

is_sosu = [1] * (max_r + 1)
is_sosu[0] = is_sosu[1] = 0
for i in range(2, max_r+1):
    if is_sosu[i]:
        for j in range(i*i, max_r+1, i):
            is_sosu[j] = 0

sums = [0] * (max_r + 1)
for i in range(1, max_r+1):
    if is_sosu[i] and is_sosu[(i+1)//2]:
        sums[i] = sums[i-1] + 1
    else:
        sums[i] = sums[i-1]

for i in range(Q):
    print((sums[r[i]] - sums[l[i]-1]))
# Original solution
def get_sieve_of_eratosthenes_new(n):
    import math
    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]

primelist=get_sieve_of_eratosthenes_new(10**5)
subprimelist=[(primelist[i]+1)//2 for i in range(0,len(primelist))]
primeset=set(primelist)
subprimeset=set(subprimelist)
real=list(primeset&subprimeset)
real=[2*real[i]-1 for i in range(0,len(real))]
real=set(real)

Q=int(eval(input()))
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
    l[i],r[i]=list(map(int,input().split()))
for i in range(0,Q):
    test={i for i in range(l[i],r[i]+1)}
    print((len(test&real)))

# Optimized solution
def get_sieve_of_eratosthenes_new(n):
    import math
    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]

primelist=get_sieve_of_eratosthenes_new(10**5)
subprimelist=[(primelist[i]+1)//2 for i in range(0,len(primelist))]
primeset=set(primelist)
subprimeset=set(subprimelist)
real=list(primeset&subprimeset)
real=[2*real[i]-1 for i in range(0,len(real))]
real.sort()

Q=int(eval(input()))
l=[0]*Q
r=[0]*Q
for i in range(0,Q):
    l[i],r[i]=list(map(int,input().split()))
for i in range(0,Q):
    if r[i]<3 or l[i]>99877:
        print((0))
    else:
        s=0
        t=0
        start=0
        end=len(real)-1
        while end-start>1:
            test=(end+start)//2
            if real[test]>=l[i]:
                end=test
            else:
                start=test
        if real[start]>=l[i]:
            s=start
        else:
            s=end
        start=0
        end=len(real)-1
        while end-start>1:
            test=(end+start)//2
            if r[i]>=real[test]:
                start=test
            else:
                end=test
        if r[i]>=real[end]:
            t=end
        else:
            t=start
        print((t-s+1))
# Original solution
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(pow(n, 0.5)) + 1):
        if n % k == 0:
            return False
    return True


def resolve():
    q = int(eval(input()))
    LR = [list(map(int, input().split())) for _ in range(q)]

    Lile_2017 = [0] * (10 ** 5 + 1)
    prime = set()
    for n in range(1, 10 ** 5 + 1):
        flg1, flg2 = False, False
        if n % 2 != 0:
            if n is not prime:
                if is_prime(n):
                    flg1 = True
                    prime.add(n)
                else:
                    flg1 = False
            else:
                flg1 = True

            if (n + 1) // 2 is not prime:
                if is_prime((n + 1) // 2):
                    flg2 = True
                    prime.add((n + 1) // 2)
                else:
                    flg2 = False
            else:
                flg2 = True

        if flg1 and flg2:
            Lile_2017[n - 1] = 1

    Ruiseki = [0]
    for i in range(1, 10 ** 5 + 1):
        Ruiseki.append(Ruiseki[-1] + Lile_2017[i - 1])

    for i in range(q):
        l, r = LR[i]
        print((Ruiseki[r] - Ruiseki[l - 1]))


if __name__ == '__main__':
    resolve()


# Optimized solution
# https://atcoder.jp/contests/abc084/tasks/abc084_d
# D - 2017-like Number
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


# 素数判定
def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(pow(n, 0.5)) + 1):
        if n % k == 0:
            return False
    return True


def resolve():
    q = int(eval(input()))
    LR = [list(map(int, input().split())) for _ in range(q)]

    # 1であれば2017に似た整数、0であれば2017に似ていない数字
    Lile_2017 = [0] * (10 ** 5 + 1)

    # 素数判定済み配列
    prime = set()
    not_prime = set()

    # 1~100000が2017に似た数かどうか判定する
    for n in range(1, 10 ** 5 + 1):
        flg1, flg2 = False, False
        if n % 2 != 0:
            if n in prime:
                flg1 = True
            elif n in not_prime:
                flg1 = False
            else:
                flg1 = is_prime(n)
                prime.add(n) if flg1 else not_prime.add(n)

            if (n + 1) // 2 in prime:
                flg2 = True
            elif (n + 1) // 2 in not_prime:
                flg2 = False
            else:
                flg2 = is_prime((n + 1) // 2)
                prime.add((n + 1) // 2) if flg1 else not_prime.add((n + 1) // 2)

        Lile_2017[n - 1] += 1 if flg1 and flg2 else 0

    # 2017に似た数の累積和配列を作る
    Ruiseki = [0]
    for i in range(1, 10 ** 5 + 1):
        Ruiseki.append(Ruiseki[-1] + Lile_2017[i - 1])

    # クエリに答える
    for l, r in LR:
        print((Ruiseki[r] - Ruiseki[l - 1]))


if __name__ == '__main__':
    resolve()
# Original solution
# https://atcoder.jp/contests/abc084/tasks/abc084_d
# D - 2017-like Number
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


# 素数判定
def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(pow(n, 0.5)) + 1):
        if n % k == 0:
            return False
    return True


def resolve():
    q = int(eval(input()))
    LR = [list(map(int, input().split())) for _ in range(q)]

    # 1であれば2017に似た整数、0であれば2017に似ていない数字
    Lile_2017 = [0] * (10 ** 5 + 1)

    # 素数判定済み配列
    prime = set()
    not_prime = set()

    # 1~100000が2017に似た数かどうか判定する
    for n in range(1, 10 ** 5 + 1):
        flg1, flg2 = False, False
        if n % 2 != 0:
            if n in prime:
                flg1 = True
            elif n in not_prime:
                flg1 = False
            else:
                flg1 = is_prime(n)
                prime.add(n) if flg1 else not_prime.add(n)

            if (n + 1) // 2 in prime:
                flg2 = True
            elif (n + 1) // 2 in not_prime:
                flg2 = False
            else:
                flg2 = is_prime((n + 1) // 2)
                prime.add((n + 1) // 2) if flg1 else not_prime.add((n + 1) // 2)

        Lile_2017[n - 1] += 1 if flg1 and flg2 else 0

    # 2017に似た数の累積和配列を作る
    Ruiseki = [0]
    for i in range(1, 10 ** 5 + 1):
        Ruiseki.append(Ruiseki[-1] + Lile_2017[i - 1])

    # クエリに答える
    for l, r in LR:
        print((Ruiseki[r] - Ruiseki[l - 1]))


if __name__ == '__main__':
    resolve()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def is_prime(n):
        if n == 1:
            return False
        for k in range(2, int(pow(n, 0.5)) + 1):
            if n % k == 0:
                return False
        return True

    q = int(eval(input()))
    primes = set()
    nums = set()
    for i in range(2, 10 ** 5 + 1):
        if is_prime(i):
            primes.add(i)
            if (i + 1) // 2 in primes:
                nums.add(i)

    cnt = [0]
    for i in range(1, 10 ** 5 + 1):
        op = 1 if i in nums else 0
        cnt.append(cnt[-1] + op)

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


if __name__ == '__main__':
    resolve()
# Original solution
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


q = int(eval(input()))
lrl = []
for _ in range(q):
    lrl.append(list(map(int, input().split())) )

primes = set(get_sieve_of_eratosthenes(10**5))
like2017s = []
cnt_dict = {}
cnt_dict[-1] = 0
for i in range(10**5//2):
    num = i*2+1
    num2 = (num+1)//2
    if num in primes and num2 in primes:
        cnt_dict[num] = cnt_dict[num-2]+1
    else:
        cnt_dict[num] = cnt_dict[num-2]

for lr in lrl:
    l,r = lr
    print((cnt_dict[r]-cnt_dict[l-2]))

# Optimized solution
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

sums = [0,0,0]
curr_sum = 0
ps = primes(10**3)
pset = set(ps)
for i in range(3,10**5+1):
    for p in ps:
        if i%p == 0 and i not in pset:
            break
        if ((i+1)//2)%p == 0 and ((i+1)//2) not in pset:
            break
    else:
        curr_sum += 1
        # print(i)
    sums.append(curr_sum)
    

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

for a in ansl: print(a)

# print(sums[:54])
# Original solution
import math
Q = int(eval(input()))
l_r = [list(map(int, input().split())) for _ in range(Q)]

def isprime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
def like(x):
    if isprime(x) and isprime((x+1)//2):
        return True
    
    return False

x_list = [0] * (10 ** 5)
for i in range(1, 10**5, 2):
    if like(i):
        x_list[i] = 1

for i in range(Q):
    print((sum(x_list[l_r[i][0]: l_r[i][1]+1])))

# Optimized solution
import math
import sys
sys.setrecursionlimit(10000000)
Q = int(eval(input()))
l_r = [list(map(int, input().split())) for _ in range(Q)]

prime = []
def isprime(n):
    if n in prime:
        return True
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    
    return True


def like(x):
    if isprime(x) and isprime((x+1)//2):
        return True
    
    return False

x_dict = {1:0}
def count_like(x):
    if x in x_dict:
        return x_dict[x]
    x_dict[x] = count_like(x-1) + like(x)
    return x_dict[x]

for i in range(Q):
    print((count_like(l_r[i][1]) - count_like(l_r[i][0]) + int(like(l_r[i][0]))))
# Original solution
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return {i for i in range(n + 1) if is_prime[i]}



n = 10 ** 5
prime_set = primes(n)
q = I()
C = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 and i in prime_set and (i + 1) // 2 in prime_set:
        C[i] = 1


acc = list(accumulate(C))
for i in range(q):
    l, r = LI()
    print((acc[r] - acc[l - 1]))


# Optimized solution
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return {i for i in range(n + 1) if is_prime[i]}



n = 10 ** 5
prime_set = primes(n)
q = I()
C = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 and i in prime_set and (i + 1) // 2 in prime_set:
        C[i] = 1


acc = list(accumulate(C))
for i in range(q):
    l, r = LI()
    print((acc[r] - acc[l - 1]))
# Original solution
import math
isPrime = [True for i in range(10**5+1)]
for i in range(3, 10**5+1):
    for j in range(2, math.floor(math.sqrt(i))+1):
        if i % j == 0:
            isPrime[i] = False

cntPrime = [0 for i in range(10**5+1)]
for i in range(2,10**5+1):
    if i % 2 == 1 and isPrime[i] and isPrime[(i+1)//2]:
        cntPrime[i] = cntPrime[i-1]+1
    else:
        cntPrime[i] = cntPrime[i-1]

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


# Optimized solution
import math
prime = [i for i in range(2, 10**5+1)]
for i in range(2, math.floor(math.sqrt(10**5))+1):
    prime = [p for p in prime if (p == i or p % i != 0)]
isPrime = [False for i in range(10**5+1)]
for p in prime:
    isPrime[p] = True
cntPrime = [0 for i in range(10**5+1)]
for i in range(2, 10**5+1):
    if i % 2 == 1 and isPrime[i] and isPrime[(i+1)//2]:
        cntPrime[i] = cntPrime[i-1]+1
    else:
        cntPrime[i] = cntPrime[i-1]

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

r_max = max(r) + 10
is_prime = [True] * (r_max+1)
is_prime[0] = is_prime[1] = False
for i in range(2, r_max):
    if is_prime[i]:
        for j in range(2, r_max // i + 1):
            is_prime[i*j] = False

# print(is_prime)
a = [0] * r_max
for i in range(3, r_max):
    a[i] = a[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] += 1
# print(a)

for i in range(q):
    print((a[r[i]] - a[l[i]-1]))


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


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


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

r_max = max(r)
is_prime = eratosthenes(r_max)
a = [0] * (r_max + 1)
for i in range(3, r_max + 1):
    a[i] = a[i - 1]
    if is_prime[i] and is_prime[(i + 1) // 2]:
        a[i] += 1
# print(a)

for i in range(q):
    print((a[r[i]] - a[l[i] - 1]))
# Original solution
Q = int(eval(input()))
lr = []
maxr = 0
for i in range(Q):
    l,r = list(map(int,input().split()))
    maxr = max(maxr,r)
    lr.append([l,r])
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
prime2 = primes(maxr)
prime = [i for i in prime2 if (i+1)/2 in prime2]
import bisect
for l,r in lr:
    print((bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1)))

# Optimized solution
Q = int(eval(input()))
lr = []
maxr = 0
for i in range(Q):
    l,r = list(map(int,input().split()))
    maxr = max(maxr,r)
    lr.append([l,r])
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(3,n + 1) if is_prime[i] and is_prime[(i+1)//2]]
prime = primes(maxr)
import bisect
for l,r in lr:
    print((bisect.bisect_right(prime,r)-bisect.bisect_right(prime,l-1)))
# Original solution
q=int(eval(input()))
M=100000

import math
def erato(n):
    prime=[]
    cnt=[0]*n
    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]

prime=erato(M)
cnt=[0]*M
for i in range(len(prime)):
  cnt[prime[i]]+=0.6
  if 2*prime[i]-1<M:
    cnt[2*prime[i]-1]+=0.6
 
for i in range(1,M):
  if cnt[i]>1:
    cnt[i]=cnt[i-1]//1+1
  else:
    cnt[i]=cnt[i-1]//1
    
#print(cnt)
for i in range(q):
  l,r=list(map(int,input().split()))
  print((cnt[r]-cnt[l-1]))
  

# Optimized solution
INF = 10 ** 10
q=int(eval(input()))
M=100000

def erato(n):
    primes = [0] * 2 + [1] * (n - 1)
    for i in range(4,n + 1,2):
        primes[i] = 0
    for i in range(3,n + 1,2):
        if i * i > n:
            break
        if primes[i]:
            for j in range(i * i,n + 1,i):
                primes[j] = 0

    ret = []
    for i in range(2,n + 1):
        if primes[i]:
            ret.append(i)
    return ret

prime=erato(M)
cnt=[0]*M
for i in range(len(prime)):
  cnt[prime[i]]+=0.6
  if 2*prime[i]-1<M:
    cnt[2*prime[i]-1]+=0.6
 
for i in range(1,M):
  if cnt[i]>1:
    cnt[i]=cnt[i-1]//1+1
  else:
    cnt[i]=cnt[i-1]//1
    
#print(cnt)
for i in range(q):
  l,r=list(map(int,input().split()))
  print((cnt[r]-cnt[l-1]))
# Original solution
import math
Q=int(eval(input()))
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=list(map(int,input().split()))
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
R=[S[:i+1].count(True) for i in range(M+1)]
for i in range(Q):
    print((R[r[i]]-R[l[i]-1]))


# Optimized solution
import math
Q=int(eval(input()))
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=list(map(int,input().split()))
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
R=[0 for i in range(M+1)]
k=0
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
            k+=1
    R[i]=k
for i in range(Q):
    print((R[r[i]]-R[l[i]-1]))