CodeEff/ECCO huggingface dataset:
# Original solution
def prime_table(m):
    t = [True] * (m + 1)
    i = 2
    while i * i <= m:
        if t[i]:
            j = i + i
            while j <= m:
                t[j] = False
                j += i
        i += 1
    return t
    # t[i] = i が素数ならTrue


Q = int(eval(input()))
pt = prime_table(10 ** 5)
sn = [False] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    sn[i] = pt[i] and pt[(i + 1) // 2]
c = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    c[i] = c[i - 2] + (1 if sn[i] else 0)
    # print(i, c[i])
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((c[r] - c[l - 2]))

# Optimized solution
class Sieve:
    """区間[2,n]の値を素因数分解する"""

    def __init__(self, n=1):
        primes = []
        f = [0] * (n + 1)
        f[0] = f[1] = -1
        for i in range(2, n + 1):  # 素数を探す
            if f[i]: continue
            primes.append(i)
            f[i] = i  # 素数には自身を代入
            for j in range(i * i, n + 1, i):  # 合成数に素因数を書き込む
                if not f[j]:
                    f[j] = i  # 最小の素因数を代入
        self.primes = primes
        self.f = f

    # def is_prime(self, x) -> bool:  # 素数判定
    #     return self.f[x] == x
    #
    # def factor_list(self, x) -> list:  # 素因数分解の昇順リスト, [2,2,3,5,...]
    #     res = []
    #     while x != 1:
    #         res.append(self.f[x])
    #         x //= self.f[x]
    #     return res
    #
    # def factor(self, x) -> list:  # 素因数分解の頻度リスト, [[2,x],[3,y],[5,z],...]
    #     fl = self.factor_list(x)
    #     if not fl: return []
    #     res = [[fl[0], 0]]
    #     for p in fl:
    #         if res[-1][0] == p:
    #             res[-1][1] += 1
    #         else:
    #             res.append([p, 1])
    #     return res


def main():
    import sys

    input = sys.stdin.readline

    sieve = Sieve(10 ** 5)
    prime_set = set(sieve.primes)

    acc = [0] * (10 ** 5 + 1)
    cnt = 0
    for x in range(1, 10 ** 5 + 1):
        if (x % 2 == 1) and (x in prime_set) and ((x + 1) // 2 in prime_set):
            cnt += 1
        acc[x] = cnt

    q = int(eval(input()))
    for _ in range(q):
        left, right = list(map(int, input().split()))  # [left,right]<=10**5
        res = acc[right] - acc[left - 1]
        print(res)


if __name__ == '__main__':
    main()
# Original solution
def get_prime_list(n):
    l = [0 for _ in range(n)]
    i = 1
    while (i < n):
        for j in range(2, int((i + 1)**0.5) + 1):
            if not (i + 1) % j:
                break
        else:
            l[i] = 1
        i += 1

    return l


n_max = 10**5
is_prime = get_prime_list(n_max)
is_2017 = [0 for _ in range(n_max)]
for i in range(2, n_max + 1):
    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:
        is_2017[i - 1] = 1

s = [0]
for i in range(n_max):
    s.append(s[i] + is_2017[i])

q = int(eval(input()))
for _ in range(q):
    li, ri = list(map(int, input().split()))
    print((s[ri] - s[li - 1]))

# Optimized solution
def erat(n):
    l = [0, 0] + [1 for _ in range(n - 1)]
    i = 2
    while (i < n + 1):
        if l[i] == 1:
            for j in range(i**2, n + 1, i):
                l[j] = 0
        i += 1

    return l


n_max = 10**5
is_prime = erat(n_max)
is_2017 = [0 for _ in range(n_max + 1)]
for i in range(2, n_max + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        is_2017[i] = 1

s = [0]
for i in range(1, n_max + 1):
    s.append(s[i - 1] + is_2017[i])

q = int(eval(input()))
for _ in range(q):
    li, ri = list(map(int, input().split()))
    print((s[ri] - s[li - 1]))
# Original solution
# coding: utf-8
from bisect import bisect_left, bisect_right
def check(x):
    flag = True
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            flag = False
            break
    return flag

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]]
def primes_plus(l):
    # l: 素数の配列
    L = []
    for p in l:
        if check((p+1)//2):
            L.append(p)
    return L
l_primes = primes(10**6)
l_primes = primes_plus(l_primes)[1:]
# print(len(l_primes))
Q = int(eval(input()))
for i in range(Q):
    ans = 0
    l, r = list(map(int, input().split()))
    r += 1
    l_idx = bisect_left(l_primes, l)
    r_idx = bisect_left(l_primes, r)
    # print(l_idx, r_idx)
    if l == r and l_idx == r_idx and l == l_primes[l_idx]:
        print((1))
    else:
        print((r_idx - l_idx))
# print(l_primes)

# Optimized solution
# coding: utf-8
from bisect import bisect_left, bisect_right
def eratosthenes(N):
    # 素数判定
    flag = True
    for i in range(2, int(N**0.5) + 1):
        if N % i == 0:
            flag = False
            break
    return flag

def make_prime_nums(N):
    # Nまでの素数のリストを作成
    prime_tf = [True for _ in range(N+1)]
    prime_tf[0] = False
    prime_tf[1] = False
    for i in range(N+1):
        if prime_tf[i]:
            if eratosthenes(i):
                for j in range(i*2, N+1, i):
                    prime_tf[j] = False
    primes = [i for i in range(N+1) if prime_tf[i]]
    return primes

def make_prime_new(L):
    new_primes = []
    for l in L:
        tmp = (l+1) // 2
        if eratosthenes(tmp):
            new_primes.append(l)
    return new_primes

primes = make_prime_nums(10**5)
primes = make_prime_new(primes)[1:]
# print(primes)
N = int(eval(input()))
for _ in range(N):
    l, r = list(map(int, input().split()))
    r += 1
    l_idx = bisect_left(primes, l)
    r_idx = bisect_left(primes, r)
    if l == r and l_idx == r_idx and l == primes[l_idx]:
        print((1))
    else:
        print((r_idx - l_idx))
# Original solution
from math import sqrt
# エラトステネスのふるい
def sieve(n):
  if n <2:
    return [False]*(n)
  is_prime = [True]*(n)
  is_prime[0], is_prime[1] = False, False
  for i in range(2, int(sqrt(MAX))):
    if is_prime[i]:
      for j in range(i*2, n, i):
        is_prime[j] = False
  return is_prime
    
# 2017-like 数かどうか
MAX = 10**5
is_prime = sieve(MAX)
a = [0]*(MAX)
for i in range(MAX):
  if i%2 == 0:
    continue
  if is_prime[i] and is_prime[(i+1)//2]:
    a[i] = 1

#  累積和
s = [0]*(MAX+1)
for i in range(MAX):
  s[i+1] = s[i] + a[i]
  
# クエリ処理
Q = int(eval(input()))
for q in range(Q):
  l, r = list(map(int, input().split()))
  print((s[r+1] - s[l]))


# Optimized solution

def resolve():
    # エラトステネスのふるい
    def make_primes_table(n):
        if n < 2:
            return [False]*n
        is_prime = [True]*n
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n**0.5)):
            if is_prime[i]:
                for j in range(i**2, n, i):
                    is_prime[j] = False
        return is_prime

    MAX_N = 10**5+1
    primes_table = make_primes_table(MAX_N)
    cnt = [0]*MAX_N
    for i in range(2, MAX_N):
        if primes_table[i] and primes_table[(i+1)//2]:
            cnt[i] += 1

    for i in range(1, MAX_N):
        cnt[i] += cnt[i-1]

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

if __name__ == "__main__":
    resolve()
# Original solution
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def check(n):
    if n == 1:
        return False
    i = 2
    while i*i <= n:
        if n%i == 0:
            return False
        i += 1
    return True
f = [0 for i in range(100001)]
for i in range(1,100001):
    f[i] += f[i-1]
    if check(i):
        if check((i+1)//2):
            f[i] += 1
q = I()
for i in range(q):
    l,r = LI()
    print((f[r]-f[l-1]))

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve


# Optimized solution
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(100001)]
    for i in range(1,100001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print((f[r]-f[l-1]))

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()
# Original solution
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
if __name__ == "__main__":
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(100001)]
    for i in range(1,100001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print((f[r]-f[l-1]))

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve


# Optimized solution
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = 10**5+1
    p = 2
    f = [1]*(n+1)
    f[0] = 0
    f[1] = 0
    while p <= n:
        while p <= n and not f[p]:
            p += 1
        j = 2*p
        while j <= n:
            f[j] = 0
            j += p
        p += 1
    s = [1 if f[i] and f[(i+1)>>1] and i&1 else 0 for i in range(n+1)]
    for i in range(n):
        s[i+1] += s[i]
    q = I()
    for _ in range(q):
        l,r = LI()
        print((s[r]-s[l-1]))
    return

#Solve
if __name__ == "__main__":
    solve()
# Original solution
from math import sqrt


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


Q = int(eval(input()))

for i in range(Q):
    l, r = list(map(int, input().split()))
    count = 0
    for j in range(l, r+1, 2):
        count += is_prime(j) * is_prime((j+1)//2)
    print(count)

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

Q = int(eval(input()))

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


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


max_r = max(R)
ps = primes(max_r)

S = [0]
for i in range(1, max_r+1):
    if i in ps:
        S.append(S[i-1]+1)
    else:
        S.append(S[i-1])


for i in range(Q):
    print((S[R[i]] - S[L[i]-1]))
# Original solution
# -*- coding: utf-8 -*-

from math import sqrt

# 素数判定用関数
def is_prime2(num):
    if num < 2:
        return False
    if num == 2 or num == 3 or num == 5:
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False
    # 疑似素数(2でも3でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    num_sqrt = sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step
    return True

# 同じ数2回素数判定やりたくないのでここに保存
prime = [is_prime2(i) for i in range(100001)]
# 2017に似た数
like2017 = [0] * 100001
for i in range(1, 100001, 2):
    if prime[i] and prime[(i+1)//2]:
        like2017[i] = 1
# 累積和
sm = [0] * 100001
for i in range(1, 100001):
    sm[i] = sm[i-1] + like2017[i]

Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    # 累積和から各QはO(1)で出せる
    print((sm[r]-sm[l-1]))


# Optimized solution
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def eratosthenes_sieve(n):
    """ 素数列挙(エラトステネスの篩) """

    table = [0] * (n + 1)
    prime_list = []
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    return prime_list

N = 100000
primes = set(eratosthenes_sieve(N+1))

A = [0] * (N+1)
for a in range(1, N+1, 2):
    if a in primes and (a+1)//2 in primes:
        A[a] = 1

acc = [0] + list(accumulate(A))
for i in range(INT()):
    l, r = MAP()
    ans = acc[r+1] - acc[l]
    print(ans)
# Original solution
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def eratosthenes_sieve(n):
    """ 素数列挙(エラトステネスの篩) """

    table = [0] * (n + 1)
    prime_list = []
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    return prime_list

N = 100000
primes = set(eratosthenes_sieve(N+1))

A = [0] * (N+1)
for a in range(1, N+1, 2):
    if a in primes and (a+1)//2 in primes:
        A[a] = 1

acc = [0] + list(accumulate(A))
for i in range(INT()):
    l, r = MAP()
    ans = acc[r+1] - acc[l]
    print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def eratosthenes_sieve(n):
    """ 素数列挙(エラトステネスの篩) """

    table = [0] * (n + 1)
    prime_list = []
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    return prime_list

MAX = 10 ** 5
# 素数列挙
primes = set(eratosthenes_sieve(MAX))
acc = [0] * (MAX+1)
for a in range(3, MAX+1, 2):
    # 条件を満たす数を確認
    if a in primes and (a + 1) // 2 in primes:
        acc[a] = 1
# 累積和
acc = list(accumulate(acc))

for i in range(INT()):
    l, r = MAP()
    # 各クエリO(1)で対応
    ans = acc[r] - acc[l-1]
    print(ans)
# Original solution
Q = int(eval(input()))
memo = [0]*(10**5+1)
def eratos2():
    primes = []
    for i in range(2, 10**4):
        flag = True
        for p in primes:
            if i%p == 0:
                flag = False
        if flag:
            primes.append(i)
    return primes
D = eratos2()

for i in range(1, 10**5+1):
    if i in D and (i+1)//2 in D:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1]

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

# Optimized solution
Q = int(eval(input()))
memo = [0]*(10**5+1)

def is_prime(N):
    prime = [True for _ in range(N)]
    prime[1] = False
    for i in range(2, N):
        if not prime[i]:
            continue
        j = i+i
        while j<N:
            prime[j] = False
            j += i
    return prime

prime = is_prime(10**5+1)

for i in range(1, 10**5+1):
    if prime[i] and prime[(i+1)//2]:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1]

for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((memo[r+1]-memo[l-1]))
# Original solution
N=10**5
prime=[0]*(N+1)
for n in range(2,N+1):
  if all([n%i for i in range(2,int(n**.5)+1)]):
      prime[n]=1

check=[0]*(N+1)
for n in range(N+1):
    if n%2==1 and prime[n] and prime[(n+1)//2]:
        check[n]=1

accumulate=[0]*(N+1)
for n in range(1,N+1):
    accumulate[n]=accumulate[n-1]+check[n]

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

# Optimized solution
N=10**5
prime=[1]*(N+1)
prime[0]=prime[1]=0
for i in range(2,int(N**.5)+1):
    if not prime[i]:
        continue
    for j in range(i*2,N+1,i):
        prime[j]=0

check=[0]*(N+1)
for n in range(N+1):
    if n%2==1 and prime[n] and prime[(n+1)//2]:
        check[n]=1

accumulate=[0]*(N+1)
for n in range(1,N+1):
    accumulate[n]=accumulate[n-1]+check[n]

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

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

er_list = eratosthenes(100000)
count = [0]*100000

j = 0
for i in range(er_list[-1]):
    if i == er_list[j]:
        j += 1
        if (i+1)//2 in er_list:
            count[i] = 1 
            
count = list(accumulate(count))
            
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((count[r]-count[l-1]))

# Optimized solution
import math
from itertools import accumulate

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

max_lr = 100000
er_list = eratosthenes(max_lr)
count = [0] * max_lr


for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1
            
count = list(accumulate(count))
            
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((count[r]-count[l-1]))
# Original solution
import math
from itertools import accumulate

def eratosthenes(n):
    prime_list = []
    num_list=[i for i in range(2, n+1)]
    limit = math.sqrt(n)
    while True:
        if limit <= num_list[0]:
            return prime_list + num_list
        prime_list.append(num_list[0])
        num_list = [e for e in num_list if e % num_list[0] != 0]

max_lr = 100000
er_list = eratosthenes(max_lr)
count = [0] * max_lr


for i in range(len(er_list)):
    if (er_list[i]+1)//2 in er_list:
        count[er_list[i]] = 1
            
count = list(accumulate(count))
            
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((count[r]-count[l-1]))

# Optimized solution
import math
from itertools import accumulate


def is_prime(n):
    if n == 1:
        return 0

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0

    return 1


Q = int(eval(input()))
L = [0]*Q
R = [0]*Q

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

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L, max_R+1):
    if (i % 2 == 1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print((check[R[i] - min_L + 1] - check[L[i] - min_L]))