CodeEff/ECCO huggingface dataset:
# Original solution
from itertools import *

def sieve(n):
    a = list(range(n))
    a[:2] = None, None
    for i in range(2, n):
        if i ** 2 >= n: break
        if not a[i]: continue
        for i in range(i ** 2, n, i):
            a[i] = None
    return [v for v in a if v]

def isPrime(p):
    if p < 2:
        return False
    for i in count(2):
        if i * i > p:
            return True
        if p % i == 0:
            return False

a = sieve(50000)
while True:
    n = int(input())
    if n == 0: break
    if n % 2 == 1:
        print(0)
        continue
    ct = 0
    for v in a:
        if v > n / 2: break
        if isPrime(n - v):
            ct += 1
    print(ct)

# Optimized solution
from itertools import *

def sieve(n):
    a = list(range(n))
    a[:2] = None, None
    for i in range(2, n):
        if i ** 2 >= n: break
        if not a[i]: continue
        for i in range(i ** 2, n, i):
            a[i] = None
    return a

b = sieve(50000)
a = [v for v in b if v]
while True:
    n = int(input())
    if n == 0: break
    ct = 0
    for v in a:
        if v > n / 2: break
        if b[n - v]:
            ct += 1
    print(ct)
# Original solution
MAX = 50001

is_prime = [True for _ in range(MAX)]
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX ** (1 / 2)) + 1):
  if is_prime[i]:
    for j in range(i ** 2, MAX, i):
      is_prime[j] = False

primes = [i for i in range(MAX) if is_prime[i]]

def main():
  while True:
    n = int(eval(input()))
    if not n:
      break
    
    primes_less_than_n = [i for i in primes if i <= n // 2]
    ans = 0
    for i in primes_less_than_n:
      if i > n // 2:
        break
      if is_prime[n - i]:
        ans += 1
  
    print(ans)

main()


# Optimized solution
MAX = 50001

is_prime = [True for _ in range(MAX)]
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX ** (1 / 2)) + 1):
  if is_prime[i]:
    for j in range(i ** 2, MAX, i):
      is_prime[j] = False

primes = [i for i in range(MAX) if is_prime[i]]

def main():
  while True:
    n = int(eval(input()))
    if not n:
      break
        
    ans = 0
    for i in primes:
      if i > n // 2:
        break
      if is_prime[n - i]:
        ans += 1
  
    print(ans)

main()
# Original solution
N = 50000
t = [1]*(N)
p = [2]
d = {2:1}
for i in range(3, N, 2):
    if t[i]:
        p.append(i)
        d[i] = 1
        for j in range(3*i, N, 2*i): t[j] = 0

while True:
    n = int(eval(input()))
    if n == 0: break

    count = 0
    if n % 2:
        if n - 2 in p: count += 1
    else:
        for p1 in p:
            if 2*p1 > n: break
            if n - p1 in d:
                count += 1
    print(count)

# Optimized solution
import sys

N = 50000
t = [1]*(N)
p = [2]
d = {2:1}
for i in range(3, N, 2):
    if t[i]:
        p.append(i)
        d[i] = 1
        for j in range(3*i, N, 2*i): t[j] = 0

while True:
    n = int(sys.stdin.readline())
    if n == 0: break

    count = 0
    if n % 2:
        if n - 2 in p: count += 1
    else:
        for p1 in p:
            if 2*p1 > n: break
            if n - p1 in d:
                count += 1
    print(count)
# Original solution
# -*- coding: utf-8 -*-

import sys
import os

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(4, N // 2 + 1, 2):
    lst[i] = False
for i in range(3, int(N ** 0.5) + 1, 2):
    if lst[i]:
        for j in range(2, N // i + 1):
            index = i * j
            if index < N:
                lst[i * j] = False

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break

    if n % 2 == 1:
        if lst[n - 2]:
            print((1))
        else:
            print((0))
    elif n == 4:
        print((1))
    else:
        counter = 0
        for i in range(1, n // 2 + 1, 2):
            prime0 = i
            prime1 = n - i
            if prime0 <= prime1 and lst[prime0] and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)

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

import sys
import os

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(2 * i, N, i):
            lst[j] = False

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print((1))
        else:
            print((0))
    elif n == 4:
        print((1))
    else:
        counter = 0
        for i in range(1, n // 2 + 1, 2):
            prime0 = i
            prime1 = n - i
            if prime0 <= prime1 and lst[prime0] and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)
# Original solution
# -*- coding: utf-8 -*-

import sys
import os

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(i * i, N, i):
            lst[j] = False

primes = [i for i in range(1, N) if lst[i]]

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print((1))
        else:
            print((0))
    elif n == 4:
        print((1))
    else:
        counter = 0
        for prime0 in primes:
            prime1 = n - prime0
            if prime0 <= prime1 and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)

# Optimized solution
import sys

N = 50001
lst = [True] * N
lst[0] = False
lst[1] = False
for i in range(2, int(N ** 0.5) + 1):
    if lst[i]:
        for j in range(i * i, N, i):
            lst[j] = False

primes = [i for i in range(1, N) if lst[i]]

for s in sys.stdin:
    n = int(s)
    if n == 0:
        break
    elif n % 2 == 1:
        if lst[n - 2]:
            print((1))
        else:
            print((0))
    elif n == 4:
        print((1))
    else:
        counter = 0
        for prime0 in primes:
            prime1 = n - prime0
            if prime0 <= prime1 and lst[prime1]:
                #print(prime0, prime1)
                counter += 1
        print(counter)
# Original solution
def sieve(n):
    primes = [True] * n
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            for j in range(i * i, n, i):
                primes[j] = False
    return [i for i in range(n) if primes[i]]

primes = sieve(50000)
ret = [0] * 50001
for i in range(len(primes)):
    for j in range(i, len(primes)):
        tmp = primes[i] + primes[j]
        if tmp > 50000:
            break
        ret[tmp] += 1
while 1:
    n = int(eval(input()))
    if n == 0:
        break
    print(ret[n])

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

primes = sieve(50000)
ret = [0] * 50001
for i in range(len(primes)):
    for j in range(i, len(primes)):
        tmp = primes[i] + primes[j]
        if tmp > 50000:
            break
        ret[tmp] += 1
while 1:
    n = int(input())
    if n == 0:
        break
    print(ret[n])
# Original solution
from itertools import *
import sys

maxnum = 50000
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in range(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in range(i*2,maxnum,i): primes[j] = False
p = [ i for i in range(maxnum) if primes[i]]

for s in sys.stdin:
    d = int(s)
    if d == 0: break
    if d % 2 == 1:
        try: p.index(d-2) ;print(1)
        except: print(0); continue
    q = [ r for r in p if r < d]
    c = 0
    for j,k in combinations_with_replacement(q,2):
        if j+k==d: c += 1
    print(c)

# Optimized solution
import sys

maxnum = 50000
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in range(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in range(i*2,maxnum,i): primes[j] = False

for s in sys.stdin:
    d = int(s)
    if d == 0: break
    cnt = 0
    for i in range(2,int(d/2+1)):
        if primes[i] and primes[d-i]: cnt += 1
    print(cnt)
# Original solution
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 225):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(eval(input()))
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print((sum(primes[n-v] for v in values[:I])))

# Optimized solution
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 225):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(eval(input()))
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print((sum(1 for v in values[:I] if primes[n-v])))
# Original solution
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(eval(input()))
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print((sum(1 for v in values[:I] if primes[n-v])))

# Optimized solution
import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(eval(input()))
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print((len([1 for v in values[:I] if primes[n-v]])))
# Original solution
import sys
f = sys.stdin

def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

sieve = create_prime(50000)

prime = []
for i in range(25001):
    if sieve[i]:
        prime.append(i)

while True:
    n = int(f.readline())
    if n == 0:
        break
    cnt = 0
    for i in prime:
        if i > n // 2 + 1:
            break
        if sieve[n - i]:
            cnt += 1
    print(cnt)

# Optimized solution
import sys
f = sys.stdin

def create_prime(n):
    prime = [1] * (n + 1)
    prime[:2] = [0, 0]
    for i in range(len(prime)):
        if prime[i]:
            for j in range(2 * i, len(prime), i):
                prime[j] = 0
    return prime

sieve = create_prime(50000)

prime = []
for i in range(25001):
    if sieve[i]:
        prime.append(i)

while True:
    n = int(f.readline())
    if n == 0:
        break
    cnt = 0
    temp = n // 2
    for i in prime:
        if i > temp:
            break
        if sieve[n - i]:
            cnt += 1
    print(cnt)
# Original solution
import math

r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

prime = []
for i in range(len(p)):
    if p[i] == 1:
        prime.append(i+1)

while True:
    n = int(input())
    if n == 0:
        break
    count = 0
    for i in prime:
        if i > n/2:
            break
        m = n - i
        if prime.count(m) == 1:
                count += 1
    print(count)

# Optimized solution
import math

r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

prime = []
for i in range(len(p)):
    if p[i] == 1:
        prime.append(i+1)

while True:
    n = int(input())
    if n == 0:
        break
    count = 0
    for i in prime:
        if i > n/2:
            break
        m = n - i
        if p[m-1] == 1:
                count += 1
    print(count)
# Original solution
def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,(n)//i+1):
        l[i*j] = 0
  l2 = [n for n in range(len(l)) if l[n]]
  return l2

l = primes(50000)
while True:
  n = int(eval(input()))
  if n == 0:
    break
  count = 0
  for i in range(1,n):
    if l[i] > n/2:
      break
    elif (n - l[i]) in l:
      count += 1
  print(count)

# Optimized solution
def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,(n)//i+1):
        l[i*j] = 0
  return l

l = primes(50000)
while True:
  n = int(eval(input()))
  if n == 0:
    break
  count = 0
  for i in range(2,n//2+1):
    if (l[i] and l[n-i]):
      count += 1
  print(count)
# Original solution
from math import sqrt, floor
from bisect import bisect_left


def search(x):
    global p, lp
    i = bisect_left(p, x)
    return i != lp and p[i] == x


p = [2]
for i in range(3, 50000, 2):
    for j in range(3, floor(sqrt(i)) + 1, 2):
        if not i % j:
            break
    else:
        p.append(i)
lp = len(p)

while True:
    n = int(eval(input()))
    if not n:
        break
    if n & 1:
        print((int(search(n - 2))))
        continue
    n2 = n // 2
    cnt = 0
    for i in p:
        if n2 < i:
            break
        if search(n - i):
            cnt += 1
    print(cnt)

# Optimized solution
from math import sqrt, floor

p = [2]
for i in range(3, 50000, 2):
    for j in range(3, floor(sqrt(i)) + 1, 2):
        if not i % j:
            break
    else:
        p.append(i)
sp = set(p)

while True:
    n = int(eval(input()))
    if not n:
        break
    if n & 1:
        print((int(n - 2 in sp)))
        continue
    n2 = n // 2
    cnt = 0
    for i in p:
        if n2 < i:
            break
        if n - i in sp:
            cnt += 1
    print(cnt)
# Original solution
def sieve(n):
    is_prime = [True] * (n + 1)
    for i in range(2,n + 1):
        if is_prime [i] == False:
            continue
        for j in range(i * 2,n + 1,i):
            is_prime [j] = False
    return {i for i in range(2,n + 1) if is_prime [i]}

prime = sieve(100000)

while True:
    N = int(eval(input()))
    if N == 0:
        break
    ans = 0
    for i in range(2,N // 2 + 1):
        if i in prime and (N - i) in prime:
            ans += 1
    print(ans)

# Optimized solution
def sieve(n):
    is_prime = [True] * (n + 1)
    for i in range(2,n + 1):
        if is_prime [i] == False:
            continue
        for j in range(i * 2,n + 1,i):
            is_prime [j] = False
    return {i for i in range(2,n + 1) if is_prime [i]}

prime = sieve(100000)
dic = {}

while True:
    N = int(eval(input()))
    if N == 0:
        break
    if N in dic:
        print((dic [N]))
        continue
    ans = 0
    for i in range(2,N // 2 + 1):
        if i in prime and (N - i) in prime:
            ans += 1
    print(ans)
    if not N in dic:
        dic [N] = ans
# Original solution
# D
from math import sqrt
def sieve(n:int)->list:
    """エラトステネスの篩"""
    if n<2:  return [False]*(n+1)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    
    return is_prime


N = int(1e5)
is_prime = sieve(N)
# like-2017
cnt = [0]*(N+1)
for i in range(1, N+1):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
    
Q = int(eval(input()))
for _ in range(Q):
    l,r = list(map(int, input().split()))
    print((cnt[r]-cnt[l-1]))

# Optimized solution
# D
from math import sqrt
def sieve(n:int)->list:
    """エラトステネスの篩"""
    if n<2:  return [False]*(n+1)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    
    return is_prime


N = int(1e5)
is_prime = sieve(N)
# like-2017
cnt = [0]*(N+1)
for i in range(1, N+1):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
    
import sys
Q = sys.stdin.readline()
for l,r in (list(map(int, line.split())) for line in sys.stdin.readlines()):
    print((cnt[r] - cnt[l-1]))
# Original solution
Q = int(eval(input()))
is_prime = {i:True for i in range(10**5+1)}
is_prime[0], is_prime[1] = False, False
for i in range(2, 10**5+1):
    if is_prime[i]:
        for j in range(i*2, 10**5+1, i):
            is_prime[j] = False
s = [0] * (10**5+1)
for i in range(1, 10**5):
    s[i+1] = s[i] + int(is_prime[i] and is_prime[(i+1)//2])
for _ in range(Q):
    left, right = list(map(int, input().split()))
    print((s[right+1]-s[left]))

# Optimized solution
Q = int(eval(input()))
is_prime = [True for i in range(10**5+1)]
is_prime[0], is_prime[1] = False, False
for i in range(2, 10**5+1):
    if is_prime[i]:
        for j in range(i*2, 10**5+1, i):
            is_prime[j] = False
s = [0] * (10**5+1)
for i in range(1, 10**5):
    s[i+1] = s[i] + int(is_prime[i] and is_prime[(i+1)//2])
for _ in range(Q):
    left, right = list(map(int, input().split()))
    print((s[right+1]-s[left]))
# Original solution
import itertools
n=int(eval(input()))
d=[list(map(int,input().split())) for i in range(n)]

sosuu=[1 for i in range(10**5+1)]
#sosuuのindexの値が1の時素数とする。
sosuu[0]=0
sosuu[1]=0
for i in range(2,10**5+1):
  if sosuu[i]==0:continue
  elif sosuu[i]==1:
    for j in range(2*i,10**5+1,i):
      sosuu[j]=0
like_n=[]
like_n+=sosuu
#奇数なので、2を削除。
like_n[2]=0
for i in range(3,10**5+1):
  if sosuu[i]==0:continue
  elif sosuu[i]==1 and sosuu[(i+1)//2]==0:
    like_n[i]=0
ans= list(itertools.accumulate(like_n))
for ans_d in d:
  print((ans[ans_d[1]]-ans[ans_d[0]-1]))



# Optimized solution
import itertools
n=int(eval(input()))
d=[list(map(int,input().split())) for i in range(n)]

sosuu=[1 for i in range(10**5+1)]
#sosuuのindexの値が1の時素数とする。
sosuu[0]=0
sosuu[1]=0
for i in range(2,int((10**5+1)**0.5)+1):
  if sosuu[i]==0:continue
  elif sosuu[i]==1:
    for j in range(2*i,10**5+1,i):
      sosuu[j]=0
like_n=[]
like_n+=sosuu
#奇数なので、2を削除。
like_n[2]=0
for i in range(3,10**5+1):
  if sosuu[i]==0:continue
  elif sosuu[i]==1 and sosuu[(i+1)//2]==0:
    like_n[i]=0
ans= list(itertools.accumulate(like_n))
for ans_d in d:
  print((ans[ans_d[1]]-ans[ans_d[0]-1]))
# Original solution
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        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 = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = list(map(int, input().split()))
 
K = max(r)
prime = prime(K)
a = [0]*K
S = a + [0]
for i in range(K):
    if i+1 in prime and (i+2)/2 in prime:
        a[i] = 1

for i in range(K):
    S[i+1] = S[i] + a[i]

for i in range(Q):
    rr, ll = r[i], l[i]
    if rr == ll:
        if a[ll-1] == 1:
            print((1))
        else:
            print((0))
    else:
        print((S[rr-1] - S[ll-1]))



# Optimized solution
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        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 = [0]*Q, [0]*Q
for i in range(Q):
    l[i], r[i] = list(map(int, input().split()))
 
K = max(r)
prime = prime(K)
a = [1]*(K+1)
s = [0]*(K+1)
a[0] = 0
a[1] = 0
for i in range(2,K+1):
    if a[i]:
        for j in range(i*i, K+1, i):
            a[j] = 0

for i in range(3,K+1,2):
    if a[i] and a[(i+1)//2]:
        s[i] = 1

for i in range(K):
    s[i+1] += s[i]

for i in range(Q):
    rr, ll = r[i], l[i]
    if rr == ll:
        if s[ll]-s[ll-2] == 1:
            print((1))
        else:
            print((0))
    else:
        print((s[rr] - s[ll-1]))
# Original solution
import math


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 = []
    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]


if __name__ == '__main__':
    data = set(get_sieve_of_eratosthenes(100000))
    pos = []
    for i in data:
        if (i + 1) % 2 == 0:
            if (i + 1) // 2 in data:
                pos.append(i)
    q = int(eval(input()))
    for _ in range(q):
        l,r = list(map(int,input().split()))
        ans = 0
        for i in pos:
            if i <= r and l <= i:
                ans += 1
        print(ans)

# Optimized solution
import math
import bisect

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 = []
    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]


if __name__ == '__main__':
    data = set(get_sieve_of_eratosthenes(100000))
    pos = []
    for i in data:
        if (i + 1) % 2 == 0:
            if (i + 1) // 2 in data:
                pos.append(i)
    pos.sort()
    q = int(eval(input()))
    for _ in range(q):
        l,r = list(map(int,input().split()))
        print((bisect.bisect_right(pos,r) - bisect.bisect_left(pos,l)))
# Original solution
d = [0]
ans = 0

def prime(n):
    if n == 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        else:
            i += 1
    return True
    
for i in range(10 ** 5 // 2):
    if prime(2 * i + 1) and prime(i + 1):
        ans += 1
    d.append(ans)

Q = int(eval(input()))

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

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

Q = int(eval(input()))
my_max = 10 ** 5

nums = [i for i in range(2, my_max + 1)]
p = 2
idx = 0
while p * p <= my_max and idx < len(nums):
    nums = [n for n in nums if n % p != 0 or n == p]
    idx += 1
    p = nums[idx]
primes = set(nums)

ruiseki = [0]
total = 0
for i in range(1, my_max + 1):
    if i % 2 == 1 and i in primes and int((i + 1) / 2) in primes:
        total += 1
    ruiseki.append(total)

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

def prime(n):
    # 素数列挙
    # nまでの素数をリストで返す(nを含む)
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5+1)):
        primes.difference_update(list(range(i*2, n+1, i)))
    primes=list(primes)
    return primes

prime_set = set(prime(10**5))
ans = []

for i in range(10**5+1):
    if i%2 == 0:
        ans.append(0)
    else:
        if i in prime_set and (i+1)//2 in prime_set:
            ans.append(1)
        else:
            ans.append(0)
ans = list(accumulate(ans))

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

# Optimized solution
from itertools import accumulate
Q = int(eval(input()))
m = 0
ls = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    m = max(m, max(l, r))
    ls.append((l, r))

def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

a = sieve_eratosthenes(m)
b = [0 for i in range(m+1)]
for i in range(2, m+1):
    if i%2 == 1 and a[i] == 1 and a[(i+1)//2] == 1:
        b[i] = 1
c = list(accumulate(b))
for l, r in ls:
    print((c[r] - c[l-1]))