Problem:
 Score : 400 points    Problem Statement We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.  You are given Q queries.  In the i -th query, given two odd numbers l_i and r_i , find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i .      Constraints  1≤Q≤10^5  1≤l_i≤r_i≤10^5  l_i and r_i are odd.  All input values are integers.         Input Input is given from Standard Input in the following format:  Q  l_1  r_1  :  l_Q  r_Q       Output Print Q lines. The i -th line (1≤i≤Q) should contain the response to the i -th query.        Sample Input 1 1
3 7      Sample Output 1 2   3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.  5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.  7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.   Thus, the response to the first query should be 2 .       Sample Input 2 4
13 13
7 11
7 11
2017 2017      Sample Output 2 1
0
0
1  Note that 2017 is also similar to 2017.       Sample Input 3 6
1 53
13 91
37 55
19 51
73 91
13 49      Sample Output 3 4
4
1
1
1
2

Solution (Python):
import bisect
Q = int(input())
lsQ = []
for i in range(Q):
    l,r = map(int,input().split())
    lsQ.append([l,r])
def prime(N):
    lsprime = [0,0]+[1 for i in range(N-1)]
    lsprime2 = []
    for i in range(N+1):
        if lsprime[i] == 0:
            continue
        lsprime2.append(i)
        k = i
        while i <= N:
            lsprime[i] = 0
            i += k
    return lsprime2

primels = prime(10**5)
primeset = set(primels)
lssim = []
for i in primels:
    x = (i+1)//2
    if x in primeset:
        lssim.append(i)
for i in range(Q):
    ans = bisect.bisect(lssim,lsQ[i][1])-bisect.bisect_left(lssim,lsQ[i][0])
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline




'''
a,b=[],[]
for i in range(n):
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

def premf(n):
    
    
    
    IsPrime=[False]+[False]+[True]*(n-1)

    res=[]
    for j in range(4,n+1,2):
        IsPrime[j]=False
    for i in range(1,n+1,2):
        if IsPrime[i]:
            for j in range(i*2,n+1,i):
                    IsPrime[j]=False

            if IsPrime[(i+1)//2]:
                res.append(i)
        
                
    
    return res

q=int(input())
n=10**5
res=premf(n)
a=[0]*(10**5+1)
t=0

for i in range(len(res)):
    t+=1
    a[res[i]]=t
for i in range(10**5):
    if a[i+1]==0:
        a[i+1]=a[i]

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

Solution (Python):
import math
q=int(input())
num=[0]*(10**5+5)
ans=[0]*(10**5+5)
num[2]=1
for i in range(3,10**5+2,2):
    yn=0
    for j in range(2,int(math.sqrt(i))+1):
        if i%j==0:
            yn=1
            break
    if yn==0:
        num[i]=1
        if num[(i+1)//2]==1:
            ans[i]=1
for i in range(1,len(num)):
    ans[i]=ans[i-1]+ans[i]
for i in range(q):
    l,r=map(int,input().split())
    print(ans[r]-ans[l-1])

Solution (Python):
import numpy as np
import bisect
def sieve_of_eratosthenes(n):
    max = int(np.sqrt(n))
    seachList = [i for i in range(2,n+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        prm = seachList[0]
        seachList = [i for i in seachList if i%prm != 0]
    primeNum.extend(seachList)
    return primeNum


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

prime_list = sieve_of_eratosthenes(max(r))

ruiseki = [0]*len(prime_list)
for i in range(len(prime_list)):
    if (prime_list[i]+1)//2 in prime_list:
        ruiseki[i] += 1 + ruiseki[i-1]
    else:
        ruiseki[i] = ruiseki[i-1]

ruiseki.insert(0,0)

for i in range(Q):
    ans = 0
    ans = ruiseki[bisect.bisect_right(prime_list,r[i])] - ruiseki[bisect.bisect_left(prime_list,l[i])]
    print(ans)

Solution (Python):
import bisect

N = 10 ** 5
primes = [True] * (N + 1)
primes[0] = primes[1] = False
for i in range(2, int(len(primes) ** 0.5 + 1)):
    for j in range(i + i, len(primes), i):
        primes[j] = False
primes = [i for i in range(len(primes)) if primes[i]]
targets = [x for x in primes if (x + 1) // 2 in primes]

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    x = bisect.bisect_left(targets, l)
    y = bisect.bisect_right(targets, r)
    print(y - x)

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


p = [False]*(10**5+1)
c = [0]*(10**5+1)

for i in range(2, len(p)):
    p[i] = isPrime(i)
    c[i] = c[i-1]
    if i % 2 == 1 and p[i] and p[i//2+1]:
        c[i] += 1

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

Solution (Python):
import bisect

def sieve(n):
    is_prime =[1]*n
    is_prime[0]=0

    for i in range(2,int((n**0.5)//1+2)):
        if is_prime[i-1]:
            j=i*2
            while j<=n:
                is_prime[j-1]=0
                j+=i
    table=[i for i in range(3,n+1) if is_prime[i-1] and is_prime[i//2]]
    return table

q=int(input())
L=sieve(10**5+1)
ans=[]

for i in range(q):
    l,r=map(int,input().split())
    ans.append(bisect.bisect_right(L,r)-bisect.bisect_left(L,l))

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

Solution (Python):
import bisect

def sieve(n):
    is_prime =[1]*n
    is_prime[0]=0

    for i in range(2,int((n**0.5)//1+2)):
        if is_prime[i-1]:
            j=i*2
            while j<=n:
                is_prime[j-1]=0
                j+=i
    table=[i for i in range(3,n+1) if is_prime[i-1] and is_prime[i//2]]
    return table

q=int(input())
L=sieve(10**5+1)
ans=[]

for i in range(q):
    l,r=map(int,input().split())
    ans.append(bisect.bisect_right(L,r)-bisect.bisect_left(L,l))

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

Solution (Python):
class Eratosthenes():  
    def __init__(self, N):  
        self.fact = [i for i in range(N + 1)]
        for i in range(2, int(N ** 0.5) + 1):
            if self.fact[i] < i:
                continue
            for j in range(i ** 2, N + 1, i):
                self.fact[j] = i
        self.prime = set(i for i in range(2, N + 1) if i == self.fact[i])


q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

p = Eratosthenes(10 ** 5).prime
acc = [0]
for i in range(1, 10 ** 5, 2):
    tmp = (i in p) and ((i + 1) // 2 in p)
    acc.append(acc[-1] + tmp)

for l, r in lr:
    ans = acc[r // 2 + 1] - acc[l // 2]
    print(ans)

Solution (Python):
q = int(input())

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

P = [0]*(10**6)

for i in range(1,10**6 - 1):
	if is_prime[i+1] == True and is_prime[(i+2)//2] == True:
		P[i+1] = P[i] + 1
	else:
		P[i+1] = P[i]

for i in range(1,q+1):
	l,r = map(int,input().split())
	print(P[r] - P[l-1])

Solution (Python):
def Sieve_of_Eratosthenes(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 is_prime
  

def is_2017like(n):
  return is_prime[n] and is_prime[(n+1)//2]

is_prime = Sieve_of_Eratosthenes(10**5)
check = [is_2017like(n) for n in range(10**5 + 1)]
ans = [0]
for i in range(1, 10**5 + 1):
  if check[i]:
    ans.append(ans[-1] + 1)
  else:
    ans.append(ans[-1])

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

Solution (Python):
import math


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


q = int(input())
l = []
r = []
for i in range(q):
    ll, rr = map(int, input().split())
    l.append(ll)
    r.append(rr)

dp = [0 for _ in range(10**5 + 5)]
dpsum = [0 for _ in range(10**5 + 5)]

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

for i in range(q):
    print(dpsum[r[i]] - dpsum[l[i] - 2])

Solution (Python):
import itertools

Q = int(input())
l = [0 for q in range(Q)]
r = [0 for q in range(Q)]
for q in range(Q):
  l[q], r[q] = map(int, input().split(' '))
max_r = max(r)
prime_numbers = [True for n in range(max_r+1)]
similar_numbers = [False for n in range(max_r+1)]
 
prime_numbers[0], prime_numbers[1] = False, False    
for divisor in range(2, max_r//2 + 1):
  if prime_numbers[divisor]:
    for multipler in range(2, max_r//divisor + 1):
      prime_numbers[divisor * multipler] = False
      
for N in range(1, max_r + 1, 2):
  if prime_numbers[N] and prime_numbers[(N+1)//2]:
    similar_numbers[N] = True
accumulate_sim_nums = list(itertools.accumulate(map(int, similar_numbers)))
    
for q in range(Q):
  print(accumulate_sim_nums[r[q]]-accumulate_sim_nums[l[q]-1])

Solution (Python):
def ERTS(N):
    table = [True]*(N+1)
    table[0], table[1] = False, False
    n = 2
    while n < N**0.5+1:
        if n:
            for i in range(n*2, N+1, n):
                table[i] = False
        n += 1
    return table

table = ERTS(10**5)
prime = []
for i in range(10**5+1):
    if table[i]:
        prime.append(i)

lst = []       
for p in prime:
    if table[(p+1)//2]:
        lst.append(p)

import bisect
Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    l = bisect.bisect_left(lst, L)
    r = bisect.bisect(lst, R)
    print(r - l)

Solution (Python):
import numpy as np

def isPrimeNum(x):
    if type(x) is not int: return False
    if x <= 1: return False
    if x <= 3: return True
    max = int(np.sqrt(x))
    for i in range(2, max+1):
        if x % i == 0: return False
    return True
    
def isNumLike2017(x):
    if isPrimeNum(x) == False: return False
    if isPrimeNum(int((x+1)/2)) == False: return False
    return True
        
N = 10**5
X = np.zeros(N+1, dtype='int64')
for i in range(1, N+1):
    if isNumLike2017(i): X[i] += 1
X = X.cumsum()

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

Solution (Python):
import numpy as np

def isPrimeNum(x):
    if type(x) is not int: return False
    if x <= 1: return False
    if x <= 3: return True
    max = int(np.sqrt(x))
    for i in range(2, max+1):
        if x % i == 0: return False
    return True
    
def isNumLike2017(x):
    if isPrimeNum(x) == False: return False
    if isPrimeNum(int((x+1)/2)) == False: return False
    return True
        
N = 10**5
X = np.zeros(N, dtype='int64')
for i in range(1, N+1):
    if isNumLike2017(i): X[i-1] += 1
X = X.cumsum()

Q = int(input())
for _ in range(Q):
    l, r = input().split()
    l, r = int(l), int(r)
    if l == 1: L = 0
    else: L = X[l-2]
    R = X[r-1]
    print(R - L)

Solution (Python):
def f():    
    dp = [1]*(10**5+1) 
    dp[0],dp[1] = 0, 0
    for i in range(2, 10**5+1):
        if dp[i] == 0:
            continue
        j = i
        while j + i <= 10**5:
            j += i
            if dp[j] == 1:
                dp[j] = 0
    
    ni = [0]*(10**5+1) 
    for i in range(2, 10**5+1):
        if dp[i] == 1 and dp[(i+1)//2] == 1:
            ni[i] = 1
    
    ru = [0]*(10**5+1)
    for i in range(1, 10**5+1):
        ru[i] = ru[i-1] + ni[i]
    
    q = int(input())
    for i in range(q):
        l, r = map(int,input().split())
        print(ru[r] - ru[l-1])

if __name__ == '__main__':
    f()

Solution (Python):
dp = [1]*(10**5+1) 
dp[0],dp[1] = 0, 0
for i in range(2, 10**5+1):
    if dp[i] == 0:
        continue
    j = i
    while j + i <= 10**5:
        j += i
        if dp[j] == 1:
            dp[j] = 0

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

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

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

Solution (Python):

import sys

end_no = 10 ** 5


def eratosthenes(N):
    prime = []  
    data = [i for i in range(2, N + 1)]

    while True:
        p = data[0]

        if p >= N ** 0.5:
            return prime + data

        prime.append(p)
        data = [i for i in data[:] if i % p != 0]


prime = eratosthenes(end_no)
prime = set(prime)


cusum = [0] * (end_no + 1)
for n in range(1, end_no + 1):
    cusum[n] = cusum[n - 1]
    if n % 2 == 0:
        continue

    if n in prime and int((n + 1) / 2) in prime:
        cusum[n] += 1



Q = int(input())

for _ in range(Q):
    l, r = map(int ,sys.stdin.readline().strip().split())
    print(cusum[r] - cusum[l - 1])

Solution (Python):
dp=[1]*(10**5+1)
dp[0],dp[1]=0,0
for i in range(2,10**5+1):
  if dp[i]==0:
    continue
  j=i
  while j+i<=10**5:
    j+=i
    if dp[j]==1:
      dp[j]-=1
      
ni=[0]*(10**5+1)
for i in range(2,10**5+1):
  if dp[i]==1 and dp[(i+1)//2]==1:
    ni[i]=1

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

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

Solution (Python):
n = int(input())

def gen_primes(limit):
    prime_table = [True] * (limit + 1)
    prime_table[0] = False
    prime_table[1] = False
    for i in range(2, int(limit**.5)+1):
        prime_table[i+i::i] = [False] * (limit//i-1)
    return prime_table

primes = gen_primes(10**5)
like2017 = [0] * len(primes)

for i in range(1, len(primes), 2):
    if primes[i] and primes[(i+1)//2]:
        like2017[i] = 1

from itertools import accumulate
like2017 = list(accumulate(like2017))
for _ in range(n):
    l,r = list(map(int, input().split()))
    print(like2017[r] - like2017[l-1])

Solution (Python):
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]
    return data

primes = set(get_sieve_of_eratosthenes(10**5))
A = []
for i in range(1, 10**5+1):
  if i % 2 == 1:
    if i in primes and (i+1) // 2 in primes:
      A.append(1)
    else:
      A.append(0)
  else:
    A.append(0)

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

q = int(input())
for _ in range(q):
  l, r = map(int, input().split())
  if l == 1:
    l = 2
  ans = A[r-1] - A[l-2]
  print(ans)

Solution (Python):
from math import ceil, sqrt


def eratosthenes(n):
    hurui = [i for i in range(n + 1)]
    for i in range(2, ceil(sqrt(n)) + 1):
        for j in range(2, ceil(sqrt(i)) + 1):
            if i == 2:
                continue
            if i % j == 0:
                break
        else:
            for k in range(i + i, n, i):
                if hurui[k] != k:
                    continue
                hurui[k] = 0
        continue
    return hurui


n = 10**5 + 200
hurui = eratosthenes(n)
hurui = [bool(i) for i in hurui]
poi = [False] * (n + 1)
for i in range(n + 1):
    poi[i] = (i % 2 == 1 and hurui[i] and hurui[(i + 1) // 2])
poi[1] = False
sa = [0]
for i in range(n + 1):
    sa.append(sa[i] + poi[i])
q = int(input())
lr = [tuple(map(int, input().split())) for i in range(q)]
for li, ri in lr:
    print(sa[ri + 1] - sa[li])

Solution (Python):
from math import ceil, sqrt

n = 10**5+200
hurui = [i for i in range(n+1)]
for i in range(2,ceil(sqrt(n))+1):
    for j in range(2,ceil(sqrt(i))+1):
        if i==2:
            continue
        if i%j == 0:
            break
    else:
        for k in range(i+i,n,i):
            if hurui[k] != k:
                continue
            hurui[k] = 0
    continue

hurui = [bool(i) for i in hurui]
poi = [False]*(n+1)
for i in range(n+1):
    
    poi[i] = (i % 2 == 1 and hurui[i] and hurui[(i+1)//2])
poi[1] = False

sa = [0]
for i in range(n+1):
    sa.append(sa[i]+poi[i])




q = int(input())
lr = [tuple(map(int,input().split())) for i in range(q)]
for li,ri in lr:
    print(sa[ri+1]-sa[li])

Solution (Python):
n=7**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
  S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(input()):l,r=map(int,input().split());print(S[r]-S[l-1])

Solution (Python):
n=7**6;P=[0,0]+[1]*n;S=[0]*n;r=range(2,n)
for i in r:
  for j in range(2*i,n,i):P[j]=0
for i in r:S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(input()):l,r=map(int,input().split());print(S[r]-S[l-1])

Solution (Python):
n=7**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
for i in range(1,n):S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(input()):l,r=map(int,input().split());print(S[r]-S[l-1])

Solution (Python):
n=8**6;P=[0,0]+[1]*n;S=[0]*n
for i in range(2,n):
  for j in range(2*i,n,i):P[j]=0
for i in range(1,n):S[i]+=(P[i]==P[(i+1)//2]==1)+S[i-1]
for _ in "_"*int(input()):l,r=map(int,input().split());print(S[r]-S[l-1])

Solution (Python):
def isPrime(x):
    ans = True

    for i in range(2, int(x**0.5)+1):
        if x%i == 0:
            ans = False
            break

    return ans

q = int(input())

queries = []
rMax = 1

for i in range(q):
    l, r = list(map(int, input().split()))

    queries.append((l, r))
    rMax = max(rMax, r)

cnt = [0] * (rMax+1)

for i in range(2, (rMax+1)//2+1):
    cnt[(2*i)-2] = cnt[(2*i)-3]

    if isPrime(i) and isPrime((2*i)-1):
        cnt[(2*i)-1] = cnt[(2*i)-2]+1
    else:
        cnt[(2*i)-1] = cnt[(2*i)-2]

for l, r in queries:
    print(cnt[r] - cnt[l-1])

Solution (Python):


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]



primes = set(get_sieve_of_eratosthenes(10**5))

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

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

Solution (Python):


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]



primes = set(get_sieve_of_eratosthenes(10**5))

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

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

Solution (Python):


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]



primes = set(get_sieve_of_eratosthenes(10**5))

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

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

Solution (Python):

import math
import sys
sys.setrecursionlimit(10**6)
q = int(input())


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


a = []
b = []
c = []
for i in range(0, 10**5+5):
    a_tmp = is_prime(i)

    if i % 2 == 0:
        b_tmp = False
    else:
        b_tmp = is_prime((i+1)//2)

    a.append(a_tmp)
    b.append(b_tmp)
    c.append(a_tmp*b_tmp)

c_sum = [0]
for i in range(1, len(c)):
    c_sum.append(c[i]+c_sum[-1])




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

Solution (Python):
import math
Q=int(input())
MAX=10**5
lim=int(math.sqrt(MAX))
primes=[2]
table=[i+1 for i in range(2,MAX,2)]
while lim>table[0]:
  primes.append(table[0])
  table=[j for j in table if j%table[0]!=0]
primes=set(primes+table)

ans=[0]*(MAX+1)
for i in range(3,MAX+1,2):
  if i in primes and (i+1)//2 in primes:
    ans[i]=1
for i in range(1,MAX+1):
  ans[i]=ans[i]+ans[i-1]
for _ in range(Q):
  l,r=map(int,input().split())
  print(ans[r]-ans[l-1])

Solution (Python):
table=[True for i in range(100000+1)]
table[0]=False
table[1]=False
for i in range(2,100000+1):
    for j in range(2,100000//i+1):
        table[i*j]=False
cnt=[0 for _ in range(100000+1)]
for i in range(1,100000+1):
    cnt[i]=cnt[i-1]
    if i%2==1 and table[i]==True and table[(i+1)//2]==True:
        cnt[i]+=1

Q=int(input())
lr=[list(map(int,input().split())) for _ in range(Q)]
for i in range(Q):
    print(cnt[lr[i][1]]-cnt[lr[i][0]-1])

Solution (Python):
import sys
input = sys.stdin.readline
from math import sqrt


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    
    
    return {2, 3}.union({3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]})


sieve = Eratosthenes(10 ** 5 + 1)
ans = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    if i in sieve and (i + 1) // 2 in sieve:
        ans[i] += 1
for i in range(3, 10 ** 5):
    ans[i + 1] += ans[i]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l - 1])

Solution (Python):
import sys
input = sys.stdin.readline
from math import sqrt


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    s = [False] * n
    for i in range(1, n // 3 - correction):
        if sieve[i]:
            s[3 * i + 1 | 1] = True
    s[2] = True
    s[3] = True
    return s


sieve = Eratosthenes(10 ** 5 + 1)
ans = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    if sieve[i] and sieve[(i + 1) // 2]:
        ans[i] += 1
for i in range(3, 10 ** 5):
    ans[i + 1] += ans[i]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l - 1])

Solution (Python):
import sys
input = sys.stdin.readline
from math import sqrt


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    s = [False] * n
    for i in range(1, n // 3 - correction):
        if sieve[i]:
            s[3 * i + 1 | 1] = True
    s[2] = True
    s[3] = True
    return s


sieve = Eratosthenes(10 ** 5 + 1)
ans = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    if sieve[i] and sieve[(i + 1) // 2]:
        ans[i] += 1
for i in range(3, 10 ** 5):
    ans[i + 1] += ans[i]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l - 1])

Solution (Python):
import sys
input = sys.stdin.readline
from math import sqrt


def Eratosthenes(n):
    """n(>=6)未満の素数列挙 """
    n, correction = n - n % 6 + 6, 2 - (n % 6 > 1)
    sieve = [True] * (n // 3)
    for i in range(1, int(sqrt(n)) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
            sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * ((n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
    
    
    return {2, 3}.union({3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]})


sieve = Eratosthenes(10 ** 5 + 1)
ans = [0] * (10 ** 5 + 1)
for i in range(3, 10 ** 5, 2):
    if i in sieve and (i + 1) // 2 in sieve:
        ans[i] += 1
for i in range(3, 10 ** 5):
    ans[i + 1] += ans[i]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l - 1])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter




from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

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

a = [0] * (10 ** 5 + 5)
for i in range(1, 10**5+1):
    a[i] = a[i-1]
    if is_prime(i) and is_prime((i+1) // 2):
        a[i] += 1
Q = ni()
for i in range(Q):
    l, r = na()
    print(a[r] - a[l-1])

Solution (Python):
import numpy as np
def eratosthenes(m):
    if m<2:
        return []
    dp=[True]*(m+1)
    sosu=[2]
    like=[0]*(m+1)
    like[3]=1
    for x in range(3,m+1,2):
        if dp[x]:
            sosu.append(x)
            if dp[(x+1)//2]==True and (x+1)//2%2==1:
                like[x]+=1
        for j in range(2*x, m+1, x):
            dp[j]=False
    return like

like=eratosthenes(10**5+1)
c = np.array(like).cumsum()
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    ans=c[r]-c[l-1]
    print(ans)

Solution (Python):
from itertools import *

MAX=10**5+1
is_prime=[True]*MAX
is_prime[0]=False
is_prime[1]=False
for i in range(2,MAX):
  if is_prime[i]==False:
    continue
  for j in range(i*2,MAX,i):
    is_prime[j]=False

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]+list(accumulate(a))

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

Solution (Python):
def prime_factor_table(n):
    table = [0] * (n + 1)

    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i

    return table

l = prime_factor_table(100000)
l[0] = 1
l[1] = 1
l2 = [0]*100000

for i in range(1,100000,2):
    x = (i+1)//2
    if l[i] == 0 and l[x] == 0:
        l2[i] = 1

l3 = [0]
for i in range(100000):
    x = l3[i] + l2[i]
    l3.append(x)

Q = int(input())
for i in range(Q):
    a,b = map(int, input().split())
    print(l3[b+1]-l3[a])

Solution (Python):
import math
import bisect
def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(100000)
l2 = []
for i in range(len(l)):
    x = l[i]
    y = (x+1)//2
    if y in l:
        l2.append(x)
        
Q = int(input())
for i in range(Q):
    a,b = map(int, input().split())
    x = bisect.bisect_left(l2, a)
    y = bisect.bisect_right(l2, b)
    print(y-x)

Solution (Python):
import numpy as np
from math import sqrt

def main():
    with open(0) as f:
        Q = int(f.readline())
        Query = [tuple(map(int, line.split())) for line in f.readlines()]
    
    p_table = makePtable(10**5)
    p_set = set(p_table)
    Like2017 = [p for p in p_table if (p+1)//2 in p_set]
    
    database = np.array([0] * (10**5+1))
    for i in Like2017:database[i] = 1
    database = database.cumsum(axis=0)
    
    for l,r in Query:
        print(database[r+1] - database[l-1])

def makePtable(N):
    table = list(range(2,N+1))
    result = []
    p = 2
    while p < sqrt(N):
        p = table[0]
        result.append(p)
        table = [x for x in table if x % p != 0]
    return result + table

main()

Solution (Python):
import bisect
q=int(input())

def sieve(n):
      is_prime = [True for _ in range(n)]
      is_prime[0] = False
  
      for i in range(2, int((n**0.5)//1+2)):
          if is_prime[i-1]:
              j = 2 * i
              while j <= n:
                  is_prime[j-1] = False
                  j += i           
      table = [ i for i in range(1, n+1) if is_prime[i-1] and is_prime[i//2]]
      return table[1:]

x=sieve(10**5+1)
ans=[]

for _ in range(q):
  l,r=map(int,input().split())
  ans.append(bisect.bisect_right(x,r)-bisect.bisect_left(x,l))

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

Solution (Python):
Q = int(input())

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

max_num = 0
for _, r in queries:
    max_num = max(max_num, r)


is_prime = [True] * (max_num + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, max_num + 1):
    if not is_prime[i]:
        continue

    cnt = 2
    while i * cnt <= max_num:
        is_prime[i * cnt] = False
        cnt += 1

nums_like = [0] * (max_num + 1)
cnt = 0
for i in range(1, max_num + 1):
    if i % 2 == 0:
        nums_like[i] = nums_like[i - 1]
    else:
        if is_prime[i] and is_prime[(i + 1) // 2]:
            cnt += 1

        nums_like[i] = cnt


for l, r in queries:
    print(nums_like[r] - nums_like[l - 1])

Solution (Python):
import bisect
q=int(input())
ans=[]

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, int((n**0.5)//1+2)):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1] and is_prime[i//2]]
    return table

l_2017=sieve(10**5+1)[1:]

for i in range(q):
    l,r=map(int,input().split())
    ans.append(bisect.bisect_right(l_2017,r)-bisect.bisect_left(l_2017,l))

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