CodeEff/ECCO huggingface dataset:
# Original solution
def sieve(n):
    is_prime =[True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i+i,n,i):
                is_prime[j] = False
    c = [0 for i in range(n+1)]
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = 1
    for i in range(n):
        c[i+1] += c[i]
    return c

def solve(l,r,c):
    return c[r]-c[l-1]



if __name__ == '__main__':
    q = int(eval(input()))
    for i in range(q):
        l,r = list(map(int,input().split()))
        c = sieve(100000)
        print((solve(l,r,c)))

# Optimized solution
def sieve(n):
    is_prime =[True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i+i,n,i):
                is_prime[j] = False
    c = [0 for i in range(n+1)]
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = 1
    for i in range(n):
        c[i+1] += c[i]
    return c

def solve(l,r,c):
    return c[r]-c[l-1]



if __name__ == '__main__':
    q = int(eval(input()))
    c = sieve(100000)
    for i in range(q):
        l,r = list(map(int,input().split()))
        print((solve(l,r,c)))
# Original solution
Q = int(eval(input()))
qs = [tuple(map(int,input().split())) for i in range(Q)]

MAXN = 10**5+10
sieve = [0,0] + [1]*MAXN
p = 2
while p*p <= MAXN:
    if sieve[p]:
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

cums = [0]
for i in range(1,MAXN):
    valid = sieve[i] and sieve[(i+1)//2]
    cums.append(cums[-1] + int(valid))

for l,r in qs:
    ans = cums[r] - cums[l-1]
    print(ans)

# Optimized solution
Q = int(input())
LR = [tuple(map(int,input().split())) for i in range(Q)]

MAXN = 10**5+10
sieve = [0,0] + [1]*MAXN
p = 2
while p*p <= MAXN:
    if sieve[p]:
        for q in range(2*p,MAXN+1,p):
            sieve[q] = 0
    p += 1

likes = [0] * MAXN
for i in range(3,MAXN,2):
    if sieve[i] and sieve[(i+1)//2]:
        likes[i] += 1
cl = [0]
for l in likes:
    cl.append(l + cl[-1])

ans = []
for l,r in LR:
    ans.append(cl[r+1] - cl[l])
print(*ans, sep='\n')
# Original solution
from itertools import accumulate

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

def main():
    Q = int(eval(input()))
    N = 10 ** 5
    num_list = [0] * (N + 5)

    for i in range(1,N+1):
        if is_prime(i) and is_prime((i+1)//2):
            num_list[i] = 1

    sum_num = [0] * (N + 6)

    for i in range(1,N+2):
        sum_num[i+1] = sum_num[i] + num_list[i]

    sum_num.pop(0)

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



main()

# Optimized solution
from itertools import accumulate

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


def main():
    N = [0] * (10 ** 5 + 1)
    for i in range(3, 10 ** 5 + 1, 2):
        if is_prime(i) and is_prime((i + 1) // 2):
            N[i] += 1

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




if __name__ == "__main__":
    main()
# Original solution
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d
AC
"""
import sys
from sys import stdin
from math import ceil, floor
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def solve(queries):
    primes = set(create_prime_list(10**5)) #  素数のテーブル、inでの判定が速くできるようにリストではなくセットにしておく
    dp = [0] * 100000

    # 1〜99,999までについて、1からのトータルで2017-likeな数字が累計でいくつあるか計算してテーブルにする
    p_num = 0
    for i in range(1, 100000, 2):
        if i in primes and ((i+1)//2) in primes:
            p_num += 1
        dp[i] = p_num

    # l 〜 r までで 2017-like数がいくつあるか求める
    for l, r in queries:
        if l == 1:
            ans = dp[r]         #  1からの場合、rまでの数がそのまま答え
        else:
            ans = dp[r] - dp[l-2] #  1〜rまでの数から 1〜l(エル)までの数を引けば、l〜rでの答えになる
        print(ans)


def main(args):
    queries = []
    Q = int(eval(input()))
    # Q = 0
    # for _ in range(100000):
    #     queries.append((1, 99999))
    queries = [list(map(int,input().split())) for _ in range(Q)]
    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])


# Optimized solution
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc084/tasks/abc084_d
AC
"""
import sys
from sys import stdin
from math import ceil, floor
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    #print('x={0}'.format(x))
    nums = [x for x in range(2, limit+1)]
    while nums[0]<=x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x%current_prime != 0]
    primes.extend(nums)
    return primes


def solve(queries):
    primes = set(create_prime_list(10**5)) #  素数のテーブル、inでの判定が速くできるようにリストではなくセットにしておく
    dp = [0] * 100000

    # 1〜99,999までについて、1からのトータルで2017-likeな数字が累計でいくつあるか計算してテーブルにする
    p_num = 0
    for i in range(1, 100000, 2):
        if i in primes and ((i+1)//2) in primes:
            p_num += 1
        dp[i] = p_num

    # l 〜 r までで 2017-like数がいくつあるか求める
    for l, r in queries:
        if l == 1:
            ans = dp[r]         #  1からの場合、rまでの数がそのまま答え
        else:
            ans = dp[r] - dp[l-2] #  1〜rまでの数から 1〜l(エル)までの数を引けば、l〜rでの答えになる
        print(ans)


def main(args):
    queries = []
    Q = int(eval(input()))
    # Q = 0
    # for _ in range(100000):
    #     queries.append((1, 99999))
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        queries.append((l, r))
    solve(queries)


if __name__ == '__main__':
    main(sys.argv[1:])
# Original solution
import math
q=int(eval(input()))
a=[]
n=10**5
for i in range(q):
    start,end=list(map(int,input().split()))
    a.append(list(range(start,end+1,2)))

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

prime_data=sieve_of_eratosthenes(n)
for i in range(q):
    ans=0
    for j in range(len(a[i])):
        if a[i][j] in prime_data and (a[i][j]+1)//2 in prime_data:
            ans+=1
    print(ans)

# Optimized solution
import math
import itertools
 
def prime_boolean_table(n):
    primes=[True]*(n+1)
    primes[0]=False
    primes[1]=False
    limit=math.floor(math.sqrt(n)+1)
    for i in range(2,limit+1):
        if primes[i]:
            for j in range(i*2,n+1,i):
                primes[j]=False
    return primes

n=10**5
q=int(eval(input()))
a=[list(map(int,input().split())) for _ in range(q)]
primes=prime_boolean_table(10**5)
c=[0]*(n+1)
for i in range(n):
    if primes[i+1] and primes[(i+2)//2]:
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
for i in range(q):
    ans=c[a[i][1]]-c[a[i][0]-1]
    print(ans)
# Original solution

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

M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

for l,r in LR:
    print((lst[r]-lst[max(l-2,0)]))


# Optimized solution

Q=int(eval(input()))
LR=[]
L,R=0,0
for i in range(Q):
    l,r=list(map(int,input().split()))
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print((lst[r]-lst[max(l-2,0)]))
# Original solution
q=int(eval(input()))
lr=[tuple(map(int,input().split())) for _ in range(q)]

n=10**5
ansl=[]
sieve=[1]*(n+1)
sieve[0],sieve[1]=0,0
for i in range(2,n):
  if sieve[i]:
    for j in range(2*i,n+1,i):
      sieve[j]=0
ans=[0]*(n+1)
for i in range(3,n):
  if sieve[i]==1 and sieve[(i+1)//2]==1:
    ans[i]=ans[i-1]+1
  else:
    ans[i]=ans[i-1]

for e in lr:
  print((ans[e[1]]-ans[e[0]-1]))


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

n=10**5
ansl=[]
sieve=[1]*(n+1)
sieve[0],sieve[1]=0,0
for i in range(2,n):
  if sieve[i]:
    sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
ans=[0]*(n+1)
for i in range(3,n):
  if sieve[i]==1 and sieve[(i+1)//2]==1:
    ans[i]=ans[i-1]+1
  else:
    ans[i]=ans[i-1]

for e in lr:
  print((ans[e[1]]-ans[e[0]-1]))
# Original solution
q=int(eval(input()))
lr=[tuple(map(int,input().split())) for _ in range(q)]

n=10**5
ansl=[]
sieve=[1]*(n+1)
sieve[0],sieve[1]=0,0
for i in range(2,n):
  if sieve[i]:
    sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
ans=[0]*(n+1)
for i in range(3,n):
  if sieve[i]==1 and sieve[(i+1)//2]==1:
    ans[i]=ans[i-1]+1
  else:
    ans[i]=ans[i-1]

for e in lr:
  print((ans[e[1]]-ans[e[0]-1]))


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

def main():
  n=10**5
  ansl=[]
  sieve=[1]*(n+1)
  sieve[0],sieve[1]=0,0
  for i in range(2,n):
    if sieve[i]:
      sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
  ans=[0]*(n+1)
  for i in range(3,n):
    if sieve[i]==1 and sieve[(i+1)//2]==1:
      ans[i]=ans[i-1]+1
    else:
      ans[i]=ans[i-1]

  for e in lr:
    print((ans[e[1]]-ans[e[0]-1]))

if __name__=='__main__':
  main()
# Original solution
q=int(eval(input()))
lr=[tuple(map(int,input().split())) for _ in range(q)]

def main():
  n=10**5
  ansl=[]
  sieve=[1]*(n+1)
  sieve[0],sieve[1]=0,0
  for i in range(2,n):
    if sieve[i]:
      sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
  ans=[0]*(n+1)
  for i in range(3,n):
    if sieve[i]==1 and sieve[(i+1)//2]==1:
      ans[i]=ans[i-1]+1
    else:
      ans[i]=ans[i-1]

  for e in lr:
    print((ans[e[1]]-ans[e[0]-1]))

if __name__=='__main__':
  main()

# Optimized solution
import sys
from itertools import accumulate

readline=sys.stdin.readline
read=sys.stdin.read

def main():
  q,*lr=list(map(int,read().split()))
  n=10**5
  ansl=[]
  sieve=[1]*(n+1)
  sieve[0],sieve[1]=0,0
  for i in range(2,n):
    if sieve[i]:
      sieve[2*i::i]=[0 for _ in range(2*i,n+1,i)]
  ans=[0]*(n+1)
  for i in range(3,n):
    if sieve[i]==1 and sieve[(i+1)//2]==1:
      #ans[i]=1
      ans[i]=ans[i-1]+1
    else:
      ans[i]=ans[i-1]
  
  #ans=list(accumulate(ans))
  for l,r in zip(*[iter(lr)]*2):
    print((ans[r]-ans[l-1]))

if __name__=='__main__':
  main()
# Original solution
q = int(input())


def is_prime(x):
    if x == 1:
        return False
    d = 2
    while d**2 <= x:
        if x % d == 0:
            return False
        d += 1
    else:
        return True

primes = []
for x in range(2, 10**5+1):
    if is_prime(x):
        primes.append(x)
        
A = [0]*(10**5+1)
for prime in primes:
    if is_prime((prime+1)//2):
        A[prime] = 1


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


ans = []
for _ in range(q):
    L, R = map(int, input().split())
    cnt = S[R]-S[L-1]
    ans.append(cnt)

print(*ans, sep='\n')


# Optimized solution
U = 10**5
is_prime = [1]*(U+1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U+1, p):
            is_prime[q] = 0

primes = [p for p, tf in enumerate(is_prime) if tf]


A = [0]*(10**5+1)
for prime in primes:
    if is_prime[(prime+1)//2]:
        A[prime] = 1


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


q = int(eval(input()))
for _ in range(q):
    L, R = list(map(int, input().split()))
    ans = S[R]-S[L-1]
    print(ans)
# Original solution
U = 10**5
is_prime = [1]*(U+1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U+1, p):
            is_prime[q] = 0

primes = [p for p, tf in enumerate(is_prime) if tf]


A = [0]*(10**5+1)
for prime in primes:
    if is_prime[(prime+1)//2]:
        A[prime] = 1


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


q = int(eval(input()))
for _ in range(q):
    L, R = list(map(int, input().split()))
    ans = S[R]-S[L-1]
    print(ans)

# Optimized solution
U = 10**5
is_prime = [1]*(U+1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U+1, p):
            is_prime[q] = 0

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


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


q = int(eval(input()))
for _ in range(q):
    L, R = list(map(int, input().split()))
    ans = S[R]-S[L-1]
    print(ans)
# Original solution
q = int(eval(input()))
a = [list(int(i) for i in input().split()) for i in range(q)]
MAX = 10**5
is_prime = [1]*MAX
for i in range(2, MAX):
    if not is_prime[i]:
        continue
    for j in range(i*2, MAX, i):
        is_prime[j] = 0
s = [0]*MAX
for i in range(3,MAX):
    s[i] = s[i-1] + 1 if is_prime[i] and is_prime[(i+1)//2] else s[i-1]
for i in range(q):
    l,r = a[i]
    print((s[r]-s[l-1]))

# Optimized solution
def main():
    q = int(eval(input()))
    a = [list(int(i) for i in input().split()) for i in range(q)]
    MAX = 10**5
    is_prime = [1]*MAX
    for i in range(2, MAX):
        if not is_prime[i]:
            continue
        for j in range(i*2, MAX, i):
            is_prime[j] = 0
    s = [0]*MAX
    for i in range(3,MAX):
        s[i] = s[i-1] + 1 if is_prime[i] and is_prime[(i+1)//2] else s[i-1]
    for i in range(q):
        l,r = a[i]
        print((s[r]-s[l-1]))

if __name__ == '__main__':
    main()
# 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]


def main():
    Q = int(eval(input()))
    LR = [list(map(int, input().split())) for _ in range(Q)]
    N = 10 ** 5

    primes = get_sieve_of_eratosthenes(N)

    t = [0 for _ in range(N + 1)]
    for p in primes:
        a, b = divmod(p + 1, 2)
        if b == 0 and a in primes:
            for i in range(p, N + 1):
                t[i] += 1

    for l, r in LR:
        print((t[r+1] - t[l-1]))


main()



# Optimized solution
import itertools


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


def main():
    Q = int(eval(input()))
    LR = [list(map(int, input().split())) for _ in range(Q)]
    N = 10 ** 5

    primes = set(get_sieve_of_eratosthenes(N))

    t = [0 for _ in range(N + 1)]
    for p in primes:
        a, b = divmod(p + 1, 2)
        if b == 0 and a in primes:
            t[p] += 1

    t = list(itertools.accumulate(t))

    for l, r in LR:
        print((t[r + 1] - t[l - 1]))


main()
# Original solution
import math

MAXN = 100001
isPrime = [True for x in range(0, MAXN)]

def findPrime():
    isPrime[1] = False
    for i in range(2, MAXN):
        if isPrime[i]:
            for j in range(i + i, int(math.sqrt(MAXN)) + 1, i):
                isPrime[j] = False

findPrime()

Q = int(eval(input()))

for i in range(Q):
    temp = 0
    l, r = list(map(int, input().split()))
    for j in range(l, r + 1, 2):
        if isPrime[j] and isPrime[(j+1)//2]:
            temp += 1
    print(temp)




# Optimized solution
MAXN = 100001
isPrime = [True for x in range(0, MAXN)]

def findPrime():
    isPrime[1] = False
    for i in range(2, MAXN):
        if isPrime[i]:
            for j in range(i + i, MAXN, i):
                isPrime[j] = False

findPrime()

cache = [0 for x in range(0, MAXN)]

pSum = 0
for i in range(1, MAXN, 2):
    cache[i] = pSum
    if isPrime[i] and isPrime[(i+1)//2]:
        cache[i] += 1
    pSum = cache[i]

Q = int(eval(input()))

for i in range(Q):
    l, r = list(map(int, input().split()))
    print((cache[r] - cache[l - 2]))
# Original solution
#自然数m以下の素数を返す
def prime_numbers(m):
    primes = set()
    n = 2
    while n <= m:
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1
    return primes

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

p = prime_numbers(max(r))
cnt = [0 for i in range(max(r)+1)]
for i in p:
    if (i + 1) // 2 in p:
        cnt[i]+=1

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

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

# 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]]

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

p = primes(max(r))
cnt = [0 for i in range(max(r)+1)]
for i in p:
    if (i + 1) // 2 in p:
        cnt[i]+=1

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

for i in range(q):
    print((cnt[r[i]] - cnt[l[i] - 1]))
# Original solution
q = int(eval(input()))

p = [True] * 100010
s = [0] * 100010
p[0] = False
p[1] = False
i = 2
while i <= 100005:
    if p[i]:
        j = i * 2
        while j <= 100005:
            p[j] = False
            j += i
    i += 1


for i in range(100005):
    if i & 1 and p[i] and p[(i + 1) // 2]:
        s[i] += 1
for i in range(100005):
    s[i + 1] += s[i]

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


# Optimized solution
from itertools import accumulate

q, *lr = list(map(int, open(0).read().split()))

p = [True] * 100010
p[0] = False
p[1] = False
i = 2
while i <= 100005:
    if p[i]:
        j = i * 2
        while j <= 100005:
            p[j] = False
            j += i
    i += 1

s = [0] * 100010
for i in range(3, 100005, 2):
    if p[i] and p[(i + 2) // 2]:
        s[i] += 1
s = tuple(accumulate(s))

for l, r in zip(*[iter(lr)] * 2):
    print((s[r] - s[l - 1]))
# Original solution
#nの素数判定
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 

q = int(eval(input()))
lr = []
minimum = float('inf')
maximum = 0
for _ in range(q):
    l, r = list(map(int, input().split()))
    minimum = min(minimum, l)
    maximum = max(maximum, r)
    lr += [[l, r]]

prime = {i: 0 for i in range(1, maximum+1)}

for i in range(1, maximum+1):
    if is_prime(i) and is_prime((i+1)//2):
        prime[i] = 1

cum_prime = {i: 0 for i in range(1, maximum+1)}
cum_prime[minimum] = prime[minimum]
for i in range(1, maximum):
    cum_prime[i+1] = prime[i+1] + cum_prime[i]

cum_prime[0] = 0
for l, r in lr:
    print((cum_prime[r]-cum_prime[l-1]))

# Optimized solution

q = int(eval(input()))
lr = [list(map(int, input().split())) for _ in range(q)]
#nの素数判定
def is_prime(n):
    if n == 1:
        return 0
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return 0
    return 1

m = 0
for l, r in lr:
    m = max(l, r, m)
prime_count = [0, 0]
for i in range(2, m+1):
    prime_count += [is_prime(i)]
similar = [0]*(m+1)
for i in range(3, m+1):
    if prime_count[i] == 1 and prime_count[(i+1)//2] == 1:
        similar[i] = 1
for i in range(m):
    similar[i+1] = similar[i+1] + similar[i]

for l, r in lr:
    print((similar[r]-similar[l-1]))
# Original solution
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(10**5):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


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

if __name__ == '__main__':
    main()

# Optimized solution
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(1, 10**5, 2):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


    q = int(eval(input()))
    for _ in range(q):
        l, r = list(map(int, input().split()))
        if l==1:
            print((res[r]))
        elif res[l]==res[l-2]:
            print((res[r]-res[l]))
        else:
            print((res[r]-res[l]+1))

if __name__ == '__main__':
    main()