CodeEff/ECCO huggingface dataset:
# Original solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}

def main():
    N = 10 ** 5
    primes = prime_numbers(N)
    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
    a = tuple(accumulate(a))

    ans = []
    Q, *LR = list(map(int, open(0).read().split()))
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(a[r] - a[l - 1])

    print(('\n'.join(map(str, ans))))

if __name__ == "__main__":
    main()

# Optimized solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    N = 10 ** 5
    primes = prime_numbers(N)
    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
    a = tuple(accumulate(a))

    ans = []
    Q, *LR = list(map(int, open(0).read().split()))
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(a[r] - a[l - 1])

    print(('\n'.join(map(str, ans))))


if __name__ == "__main__":
    main()
# Original solution
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    B = [0]
    B.extend(accumulate(A))

    Q, *LR = map(int, read().split())
    ans = [0] * Q
    for i, (l, r) in enumerate(zip(LR[::2], LR[1::2])):
        ans[i] = B[r + 1] - B[l]

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


if __name__ == '__main__':
    main()


# Optimized solution
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    N = 10 ** 5
    primes = prime_numbers(N)
    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
    a = tuple(accumulate(a))

    ans = []
    Q, *LR = list(map(int, open(0).read().split()))
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(a[r] - a[l - 1])

    print(('\n'.join(map(str, ans))))


if __name__ == "__main__":
    main()
# Original solution
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [n % 2 and n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(LR[::2], LR[1::2]):
        ans.append(A[r] - A[l - 1])

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


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [n in primes and (n + 1) // 2 in primes for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(LR[::2], LR[1::2]):
        ans.append(A[r] - A[l - 1])

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


if __name__ == '__main__':
    main()
# Original solution
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = map(int, open(0).read().split())
    ans = []
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(A[r] - A[l - 1])

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


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [1] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            p[2 * i * (i + 1) :: 2 * i + 1] = [0] * (((m - 1) - 2 * i * (i + 1)) // (2 * i + 1) + 1)

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    primes = prime_numbers(10 ** 5)
    A = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(10 ** 5 + 1)]
    A = tuple(accumulate(A))

    Q, *LR = list(map(int, open(0).read().split()))
    ans = []
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(A[r] - A[l - 1])

    print(('\n'.join(map(str, ans))))
    return


if __name__ == '__main__':
    main()
# Original solution
import math
from itertools import accumulate

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

MAX = (10**5)+1
q = int(eval(input()))
A = [1 if is_prime(i)and is_prime((i + 1)//2) else 0 for i in range(MAX) ]
S = [0] + list(accumulate(A))

Q =[]
Q_append = Q.append
for _ in range(q):
    l, r = list(map(int, input().split()))
    Q_append((l, r))

for qi in Q:  
    print((S[qi[1]+1]-S[qi[0]]))

# Optimized solution
from itertools import accumulate

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

MAX = (10**5)+1
is_prime = primes(MAX)
q = int(eval(input()))
A = [1 if is_prime[i] and is_prime[(i + 1)//2] else 0 for i in range(MAX)]
S = [0] + list(accumulate(A))

Q = []
Q_append = Q.append
for _ in range(q):
    l, r = list(map(int, input().split()))
    Q_append((l, r))

for qi in Q:
    print((S[qi[1]+1]-S[qi[0]]))
# Original solution
q=int(eval(input()))
P2017=[]
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]]
P=primes(10**5)
for p in P:
  if (p+1)//2 in P:
    P2017.append(p)
LR=[0]*(10**5)
for p in P2017:
  LR[p]+=1
for i in range(10**5-1):
  LR[i+1]+=LR[i]
for i in range(q):
  l,r=list(map(int,input().split()))
  print((LR[r]-LR[l-1]))

# Optimized solution
import sys
input=lambda: sys.stdin.readline().rstrip()
n=10**5
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
A=[0]*n
def f(x):
  return is_prime[x] and is_prime[(x+1)//2]

for i in range(3,n,2):
  if f(i):
    A[i]=A[i-2]+1
  else:
    A[i]=A[i-2]
A=[0]+A
q=int(eval(input()))
for _ in range(q):
  l,r=list(map(int,input().split()))
  print((A[r+1]-A[l-1]))
# Original solution
Q = int(eval(input()))

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

F = [1]*(10**5+1)
F[0], F[1] = 0, 0
for j in range(2, len(F)):
    if isPrime(j) == True:
        for k in range(j*2, len(F), j):
            F[k] = 0

for e in range(2, len(F))[::-1]:
    if F[e] == 1 and (e) % 2 == 1:
        if F[int((e+1)/2)] == 0:
            F[e] = 0
    else:
        F[e] = 0

t = [0]*len(F)
for a in range(len(F)-1):
    t[a+1] = t[a] + F[a]

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

# Optimized solution
# D - 2017-like Number
def isPrime(p):
    for i in range(2, int(p**0.5)+1):
        if p % i == 0:
            return False
    return True

q=int(eval(input()))
f=[1]*(10**5+1)
f[0],f[1]=0,0

for i in range(2,len(f)):
    if isPrime(i):
        for j in range(i*2,len(f),i):
            f[j]=0

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

for i in range(q):
    l,r=list(map(int,input().split()))
    print((c[r]-c[l-1]))
# Original solution
def isPrime(x):
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      return False
  return True

q=int(eval(input()))
f=[1]*(10**5+1)
f[0],f[1]=0,0
n=len(f)
for i in range(2,n):
  if isPrime(i):
    for j in range(i*2,n,i):
      f[j]=0

c=[0]*(10**5+1)
for i in range(2,10**5+1):
  if i%2==1:
    if f[i]==1 and f[(i+1)//2]==1:
      c[i]=c[i-1]+1
      continue
    c[i]=c[i-1]
  else:
    c[i]=c[i-1]
for i in range(q) :
   l,r=list(map(int,input().split()))
   print((c[r]-c[l-1]))

# Optimized solution
from itertools import accumulate
import sys
input = sys.stdin.buffer.readline


def sieve(n):
    f = []
    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
    for i in range(n+1):
        if is_prime[i]:
            f.append(i)
    return f


s = sieve(10**5)
s = set(s)
number_2017 = [0]*(10**5+1)

for i in range(1, 10**5+1):
    if i % 2 == 0:
        continue
    if i in s and (i+1)//2 in s:
        number_2017[i] = 1


acc = list(accumulate(number_2017))

Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((acc[r]-acc[l-1]))
# Original solution
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()))
L = []
R = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    L.append(l)
    R.append(r)

n2017 = set()
c2017 = [0]
total = 0
for i in range(1, 10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        total += 1
    c2017.append(total)

for i in range(Q):
    l = L[i]
    r = R[i]
    ans = (c2017[r] - c2017[l-1])
    print(ans)


# Optimized solution
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 = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    LR.append((l, r))

c2017 = [0]
total = 0
for i in range(1, 10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        total += 1
    c2017.append(total)

for i in range(Q):
    l, r = LR[i]
    ans = (c2017[r] - c2017[l-1])
    print(ans)
# Original solution
import math


def eratos(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = isPrime[1] = False
    for i in range(2, int(math.sqrt(num))):
        for j in range(2 * i, num, i):
            isPrime[j] = False
    return isPrime


def isLike(isPrime):
    n = len(isPrime)
    array = [False] * (n - 1)
    for i in range(n - 1):
        if isPrime[i] and isPrime[(i + 1) // 2]:
            array[i] = True
    return array


def cumSum(array):
    n = len(array)
    cum = [0] * (len(array))
    for i in range(1, n):
        cum[i] = cum[i - 1]
        cum[i] += 1 if array[i] else 0

    return cum


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


Q = int(eval(input()))

isPrime = eratos(10 ** 5 + 1)
array = isLike(isPrime)
cum = cumSum(array)

for i in range(Q):
    l, r = list(map(int, input().split()))
    print((solve(l, r, cum)))


# Optimized solution
thres = 10 ** 5

isPrime = [True] * (thres + 5)
isPrime[0] = isPrime[1] = False
idx = 2
while (idx * idx) <= thres:
    if isPrime[idx] is True:
        for k in range(idx + idx, thres, idx):
            isPrime[k] = False
    idx += 1

isLike = [False] * (thres + 5)
isLike[0] = False
for i in range(1, thres + 1):
    if isPrime[i] is True and isPrime[(i + 1) // 2] is True:
        isLike[i] = True

cum = [0] * (thres + 5)
cum[0] = cum[1] = 0
for i in range(1, thres + 1):
    if isLike[i] is True:
        cum[i] = cum[i - 1] + 1
    else:
        cum[i] = cum[i - 1]

q = int(eval(input()))

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

def is_prime(n):
        if n <= 0:return None
        if n == 1:return False
        sup = math.floor(pow(n,1/2))
        for i in range(2,sup+1):
                if n % i == 0:
                        return False
        return True

prime = [0]*(10**5+1)
for i in range(1,10**5+1):
        if is_prime(i):
                prime[i] = 1

for p,bit in enumerate(prime[::-1]):
        p = len(prime)-1 - p
        if bit and p % 2 == 1 and prime[(p+1)//2]:
                pass
        else:
                prime[p] = 0

acc = list(itertools.accumulate(prime))
for l,r in query:
        print((acc[r]-acc[l-1]))

# Optimized solution
import sys,math,itertools
input = sys.stdin.readline
Q = int(eval(input()))
query = [list(map(int,input().split())) for i in range(Q)]

def is_prime(n):
        if n <= 0:return None
        if n == 1:return False
        sup = math.floor(pow(n,1/2))
        for i in range(2,sup+1):
                if n % i == 0:
                        return False
        return True

prime = [0]*(10**5+1)
for i in range(1,10**5+1):
        if is_prime(i):
                prime[i] = 1

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

acc = list(itertools.accumulate(prime))
for l,r in query:
        print((acc[r]-acc[l-1]))
# Original solution
import sys,math,itertools
input = sys.stdin.readline
Q = int(eval(input()))
query = [list(map(int,input().split())) for i in range(Q)]

def is_prime(n):
        if n <= 0:return None
        if n == 1:return False
        sup = math.floor(pow(n,1/2))
        for i in range(2,sup+1):
                if n % i == 0:
                        return False
        return True

prime = [0]*(10**5+1)
for i in range(1,10**5+1):
        if is_prime(i):
                prime[i] = 1

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

acc = list(itertools.accumulate(prime))
for l,r in query:
        print((acc[r]-acc[l-1]))

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

from itertools import accumulate

import math

def is_prime(n):
    if n <= 0: return None
    if n == 1: return False
    sup = math.floor(pow(n,1/2))
    for i in range(2,sup+1):
        if n % i == 0:
            return False
    return True

Q = int(eval(input()))
query = [list(map(int,input().split())) for _ in range(Q)]

bit = [0]*(10**5+1)

for i in range(10**5+1):
    if i % 2 == 1 and is_prime(i) and is_prime((i+1)//2):
        bit[i] = 1

bit = list(accumulate(bit))

for l, r in query:
    res = bit[r] - bit[l-1]
    print(res)
# Original solution
import sys
input = sys.stdin.readline

from itertools import accumulate

import math

def is_prime(n):
    if n <= 0: return None
    if n == 1: return False
    sup = math.floor(pow(n,1/2))
    for i in range(2,sup+1):
        if n % i == 0:
            return False
    return True

Q = int(eval(input()))
query = [list(map(int,input().split())) for _ in range(Q)]

bit = [0]*(10**5+1)

for i in range(10**5+1):
    if i % 2 == 1 and is_prime(i) and is_prime((i+1)//2):
        bit[i] = 1

bit = list(accumulate(bit))

for l, r in query:
    res = bit[r] - bit[l-1]
    print(res)

# Optimized solution
def sieve(N):
    global table,prime
    table = [True]*(N+1)
    table[0] = False
    table[1] = False
    prime = []
    for i in range(2,N+1):
        if table[i]:
            prime.append(i)
            for j in range(2*i,N+1,i):
                table[j] = False

def accmulate(array):
    global cs
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]

def query(l,r):
    return cs[r+1] - cs[l]

Q = int(input())

sieve(10**5)

def judge(x):
    return x % 2 and table[x] and table[(x+1)//2]

flag = [judge(x) for x in range(0,10**5+1)]

accmulate(flag)

ans_list = []

for _ in range(Q):
    l,r = map(int,input().split())
    ans = query(l,r+1)
    ans_list.append(ans)

print(*ans_list, sep="\n")
# Original solution
n = 10**5
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

is_simular_2017 = is_prime.copy()

for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if not is_prime[(i + 1) // 2]:
            is_simular_2017[i] = False


simular_2017 = [i for i in range(len(is_simular_2017)) if is_simular_2017[i]]


Q = int(eval(input()))
LR = [list(map(int, input().split())) for _ in range(Q)]
for l, r in LR:
    count = 0
    for s in simular_2017:
        if l <= s <= r:
            count += 1
    print(count)


# Optimized solution
import bisect

n = 10**5
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

num = [0] * (n + 1)

cnt = 0
for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if is_prime[(i + 1) // 2]:
            cnt += 1
    num[i] = cnt

Q = int(eval(input()))
LR = [list(map(int, input().split())) for _ in range(Q)]

for l, r in LR:
    print((num[r] - num[l - 1]))
# Original solution
def erastotenes(n):
    prime=[2]
    limit=int(n**0.5)
    data=[i+1 for i in range(2, n, 2)]      #奇数のリストを作成
    while True:
        p=data[0]
        if p>=limit:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]


naturals=erastotenes(100000)

q=int(eval(input()))
for _ in range(q):
    left, right=list(map(int,input().split()))
    count=0
    for i in range(left, right+1):
        if i==1 or i%2==0:
            continue
        if i in naturals and int((i+1)/2) in naturals:
            count+=1
    print(count)

# Optimized solution
def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

q=int(eval(input()))
for _ in range(q):
    left, right=list(map(int,input().split()))
    print((ruiseki[right]-ruiseki[left-1]))
# Original solution
def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

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

# Optimized solution
from itertools import chain, accumulate


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


U = 10 ** 5 + 10
primes = prime_set(U)
memo = [0] * U
for i in range(1, U, 2):
    if i in primes and (i + 1) // 2 in primes:
        memo[i] = 1
memo = list(accumulate(memo))

Q = int(input())
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(memo[r] - memo[l - 1])
print(*ans, sep="\n")
# Original solution
y, m, d = list(map(int, input().split('/')))

ans = 'Heisei'
if y >= 2019:
    if m > 4:
        ans = 'TBD'

print(ans)

# Optimized solution
print(('TBD' if int(input().split('/')[1]) > 4 else 'Heisei'))
# Original solution
s = input().split("/")
for i in range(3):
    s[i] = int(s[i])
p = "TBD"
if s[0] <= 2019:
    if s[1] <= 4:
        if s[2] <= 30:
            p = "Heisei"
print(p)

# Optimized solution
s = input().split("/")
for i in range(3):
    s[i] = int(s[i])
p = "TBD"
if s[0] <= 2019 and s[1] <= 4 and s[2] <= 30:
    p = "Heisei"
print(p)
# Original solution
print(('TBD'if int(input().split('/')[1])>4 else 'Heisei'))

# Optimized solution
a,b,c=list(map(int,input().split('/')))
print(('Heisei'if b<5 else'TBD'))
# Original solution
print('Heisei') if int(input()[5:7])<=4 else print('TBD')


# Optimized solution
print(('Heisei' if int(input()[5:7])<=4 else 'TBD'))
# Original solution
print((["Heisei","TBD"][int(input()[5:7])>4]))

# Optimized solution
print((["Heisei","TBD"][input()[5:7]>"04"]))
# Original solution
s = int(input().replace("/",""))
if s<= 20190430:
  print("Heisei")
else:
  print("TBD")

# Optimized solution
y, m, d = list(map(int, input().split("/")))

if y < 2019:
    print("Heisei")
elif y == 2019 and m <= 4:
    print("Heisei")
else:
    print("TBD")