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 itertools
import math
from collections import defaultdict



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

N = int(input())
ps = primes(10**5)

sim2017 = [0] * (10**5 + 1)
di =defaultdict(lambda :False)
for p in ps:
    di[p] = True
for p in ps:
    if di[(p+1)/2]:
        sim2017[p] +=1
l = len(sim2017)
for i in range(1,l):
    sim2017[i] = sim2017[i-1] + sim2017[i]
ins = []
for i in range(N):
    a,b = list(map(int,input().split(" ")))
    ins.append((a,b))
for a,b in ins:
    print(sim2017[b] - sim2017[a-1])

Solution (Python):
import numpy as np


def solve():
    n = 10**5+1
    like = np.zeros(n, dtype='uint64')
    like[2] = 0

    p = [True] * (n)
    p[0] = False
    p[1] = False
    for i in range(4, n, 2):
        p[i] = False

    for j in range(3, n, 2):
        q = (j+1)//2
        if p[j]:
            for k in range(j*2, n, j):
                p[k] = False
            if p[q]:
                like[j] = 1
            else:
                like[j] = 0
        else:
            like[j] = 0

    return np.cumsum(like)


if __name__ == '__main__':
    q = int(input())
    accum = solve()
    for l in range(q):
        l, r = map(int, input().split())
        print(accum[r]-accum[l-1])

Solution (Python):
import math
from collections import defaultdict


def SieveofEratosthenes(N):
    if N < 2:
        raise ValueError('N should be more than 2')
    primeList = []
    limit = math.sqrt(N)
    data = [i + 1 for i in range(1, N)]
    while True:
        p = data[0]
        if limit <= p:
            return primeList + data
        primeList.append(p)
        data = [e for e in data if e % p != 0]


Q = int(input())
primeList = SieveofEratosthenes(10**5)
primeDict = defaultdict(int)
like2017Dict = defaultdict(int)
for p in primeList:
    primeDict[p] = 1
for p in primeList:
    if primeDict[(p+1)//2] == 1:
        like2017Dict[p] = 1

numPrimes = [0 for i in range(10**5+1)]
for i in range(3, 10**5+1):
    if like2017Dict[i] == 1:
        numPrimes[i] = numPrimes[i-1] + 1
    else:
        numPrimes[i] = numPrimes[i-1]


def solve(l, r):
    ans = numPrimes[r] - numPrimes[l-1]
    return ans


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

Solution (Python):
import math
def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or n%2 == 0: return False
    if n < 9: return True
    if n%3 == 0: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if n%f == 0: return False
        if n%(f+2) == 0: return False
        f +=6
    return True 

def resolve():
    Q = int(input())
    LRs = [list(map(int, input().split(" "))) for i in range(Q)]
    N = 10**5
    
    
    isSpecial = [0] * (N+1)
    for i in range(1, N+1, 2):
        if is_prime(i) and is_prime((i+1)/2):
            isSpecial[i] = 1
    
    
    sums = [0] * (N+1)
    for j in range(0, N+1):
        sums[j] = sums[j-1] + isSpecial[j]

    
    for (l, r) in LRs:
        print(sums[r+1] - sums[l-1])
        

if '__main__' == __name__:
    resolve()

Solution (Python):
from collections import defaultdict
from bisect import bisect,bisect_left
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2,n+1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i%p != 0]
    return prime
prime = eratosthenes(10**5)
p_d = defaultdict(lambda:0)
prime17 = []
for p in prime:
    p_d[p] = 1
for p in prime:
    if p_d[(p+1)/2] == 1:
        prime17.append(p)

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

Solution (Python):

import sys
import math
import bisect

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 

    
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return set(prime for prime in primes if prime != 0)


def is_prime(prime_list,a):
    return a in prime_list

def solve(Q: int, L: "List[int]", R: "List[int]"):
    prime_list = primes(10**5)

    DP = [0] * (10**5)
    for i in range(1,int(10**5)):
        DP[i] = DP[i-1]
        if is_prime(prime_list,i) and is_prime(prime_list,(i+1)//2):
            DP[i] += 1

    for l,r in zip(L,R):
        print(DP[r] - DP[l-1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    Q = int(next(tokens))  
    l = [int()] * (Q)  
    r = [int()] * (Q)  
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(Q, l, r)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate


Q = int(input())
l, r = zip(*(map(int, input().split()) for _ in range(Q)))


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


dp = list(
    accumulate(
        range(10**5 + 1),
        lambda acc, i:
            acc + 1 if is_prime[i] and is_prime[(i + 1) // 2] else
            acc
    )
)


ans = '\n'.join(
    str(dp[b] - dp[a - 1])
    for a, b in zip(l, r)
)


print(ans)

Solution (Python):
Q=int(input())
n=100000
is_prime=[1]*(n+10)
is_prime[0]=0
is_prime[1]=0
for i in range(2,n+1):
	for j in range(i*2,n+1,i):
		if is_prime[j]==False:
			continue
		is_prime[j]=0
a=[0]*(n+10)
for j in range(2,n+1):
	if is_prime[j]%2==0:
		continue
	if is_prime[j] and is_prime[int((j+1)/2)]:
		a[j]=1
s=[0]*(n+10)		
for k in range(n):
	s[k+1]=a[k]+s[k]
ans=[]
for _ in range(Q):
	l,r=map(int,input().split())
	ans.append(s[r+1]-s[l])
print(*ans,sep='\n')

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

lr=[]
q=int(input())
p=0
for i in range(q):
    a=[int(j) for j in input().split()]
    lr.append(a)
    p=max(p,a[1])
ll=eratosthenes(p)
l=set(ll)
del ll[0]
li=[0 for i in range(p+2)]

for i in ll:
    if (i+1)//2 in l:
        li[i]+=1

from itertools import accumulate
la=list(accumulate(li))

for i in range(len(lr)):
    print(la[lr[i][1]]-la[lr[i][0]-1])

Solution (Python):
Q = int(input())
lr = [[int(_) for _ in input().split()] for _ in range(Q)]

p_max = 101010
is_prime = [True] * (p_max)
is_prime[0] = is_prime[1] = False

for i in range(2, p_max):
    if not is_prime:
        continue
    for j in range(i+i, p_max, i):
        is_prime[j] = False

a = [0] * (p_max)
for i in range(p_max):
    if is_prime[i] is True and is_prime[(i+1)//2] is True:
        a[i] = 1

s = [0] * (p_max+1)
for i in range(p_max):
    s[i+1] = s[i] + a[i]

for i in lr:
    print(s[i[1]+1]-s[i[0]])

Solution (Python):
import bisect
Q = int(input())
lr = [[int(x) for x in input().split()]for _ in range(Q)]
li = [3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541, 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213, 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993, 2017, 2137, 2341, 2473, 2557, 2593, 2797, 2857, 2917, 3061, 3217, 3253, 3313, 3517, 3733, 4021, 4057, 4177, 4261, 4273, 4357, 4441, 4561, 4621, 4933, 5077, 5101, 5113, 5233, 5413, 5437, 5581, 5701, 6037, 6073, 6121, 6133, 6217, 6337, 6361, 6373, 6637, 6661, 6781, 6997, 7057, 7213, 7393, 7417, 7477, 7537, 7753, 7933, 8053, 8101, 8221, 8317, 8353, 8461, 8521, 8677, 8713, 8893, 9013, 9133, 9181, 9241, 9277, 9601, 9661, 9721, 9817, 9901, 9973, 10333, 10357, 10453, 10837, 10861, 10957, 11113, 11161, 11317, 11497, 11677, 11701, 12073, 12157, 12241, 12301, 12421, 12433, 12457, 12541, 12553, 12601, 12721, 12757, 12841, 12853, 13093, 13381, 13417, 13681, 13921, 13933, 14437, 14593, 14737, 14821, 15013, 15073, 15121, 15241, 15277, 15361, 15373, 15733, 15901, 16033, 16333, 16381, 16417, 16573, 16633, 16657, 16921, 17041, 17053, 17077, 17257, 17293, 17377, 17881, 18013, 18097, 18133, 18181, 18217, 18253, 18301, 18313, 18397, 18481, 18553, 18637, 18793, 19237, 19441, 19477, 19717, 19801, 19813, 19861, 20353, 20533, 20641, 20857, 21001, 21061, 21193, 21277, 21313, 21577, 21661, 21673, 21817, 22093, 22501, 22573, 22621, 22993, 23053, 23173, 23557, 23677, 23773, 23917, 24097, 24421, 24481, 24781, 24841, 25033, 25153, 25237, 25561, 25657, 25933, 26017, 26293, 26317, 26437, 26497, 26821, 26833, 26881, 26953, 27073, 27253, 27337, 27361, 27457, 27997, 28057, 28297, 28393, 28813, 28837, 28921, 29101, 29473, 29641, 30181, 30241, 30517, 30553, 30577, 30637, 30661, 30697, 30781, 30853, 31081, 31237, 31321, 31333, 31357, 31477, 31573, 31873, 31981, 32173, 32377, 32497, 32533, 32833, 33037, 33301, 33457, 33493, 33757, 33961, 34057, 34213, 34273, 34381, 34513, 34897, 34981, 35317, 35521, 35677, 35977, 36097, 36241, 36433, 36457, 36793, 36877, 36901, 36913, 37273, 37321, 37357, 37573, 37717, 37957, 38281, 38461, 38833, 38953, 38977, 39217, 39373, 39397, 39733, 40093, 40177, 40213, 40693, 40813, 41017, 41221, 41281, 41413, 41617, 41893, 42061, 42337, 42373, 42793, 42961, 43117, 43177, 43201, 43321, 43573, 43597, 43633, 43717, 44053, 44101, 44221, 44257, 44293, 44893, 45061, 45337, 45433, 45481, 45553, 45613, 45841, 46021, 46141, 46261, 46861, 46993, 47017, 47161, 47353, 47521, 47533, 47653, 47713, 47737, 47797, 47857, 48121, 48193, 48337, 48673, 48757, 48781, 49033, 49261, 49393, 49417, 49597, 49681, 49957, 50221, 50341, 50377, 50821, 50893, 51157, 51217, 51241, 51481, 51517, 51637, 52057, 52081, 52237, 52321, 52453, 52501, 52813, 52861, 52957, 53077, 53113, 53281, 53401, 53917, 54121, 54133, 54181, 54217, 54421, 54517, 54541, 54673, 54721, 54973, 55057, 55381, 55501, 55633, 55837, 55921, 55933, 56053, 56101, 56113, 56197, 56401, 56437, 56701, 56773, 56821, 56857, 56893, 57073, 57097, 57193, 57241, 57373, 57457, 57853, 58153, 58417, 58441, 58537, 58573, 58693, 59053, 59197, 59221, 59281, 59341, 59833, 60217, 60337, 60373, 60637, 60733, 60937, 61057, 61153, 61261, 61297, 61561, 61657, 61681, 61717, 61861, 62137, 62473, 62497, 62533, 62653, 62773, 63313, 63397, 63541, 63697, 63781, 63913, 64153, 64237, 64381, 64513, 64717, 65173, 65293, 65413, 65437, 65497, 65557, 65677, 65881, 66301, 66361, 66601, 66697, 66853, 66973, 67057, 67153, 67273, 67477, 67537, 67741, 67777, 67933, 67993, 68113, 68281, 68521, 68737, 69001, 69073, 69457, 69493, 69697, 69877, 70117, 70177, 70297, 70501, 70621, 70921, 70981, 71233, 71341, 71353, 71593, 71821, 72073, 72481, 72613, 72901, 72937, 73141, 73417, 73477, 73561, 73693, 74077, 74317, 74377, 74713, 75013, 75133, 75181, 75721, 75793, 75913, 76333, 76561, 76597, 76753, 77137, 77641, 78157, 78193, 78277, 78877, 78901, 79333, 79357, 79537, 79657, 79693, 79801, 79873, 80077, 80173, 80221, 80473, 80701, 80713, 80917, 81013, 81181, 81517, 81637, 81853, 82021, 82153, 82261, 82561, 82981, 83077, 83221, 83233, 83437, 83617, 83701, 83773, 84121, 84313, 84673, 84697, 84793, 84913, 85297, 85333, 85453, 85717, 85933, 86353, 86413, 87181, 87253, 87337, 87421, 87433, 87517, 87553, 87973, 88117, 88177, 88237, 88261, 88513, 88741, 88897, 88993, 89293, 89833, 89917, 90121, 91081, 91381, 91393, 91513, 91957, 92041, 92557, 92761, 92821, 92893, 92941, 93097, 93133, 93493, 93637, 93913, 94033, 94117, 94273, 94321, 94441, 94573, 94777, 94837, 94993, 95257, 95317, 95401, 95581, 95617, 95713, 95737, 96097, 96157, 96181, 96493, 96517, 96973, 97081, 97177, 97501, 97561, 97777, 97813, 98017, 98737, 98953, 99277, 99577, 99661, 99877]
for i in lr:
    begin = bisect.bisect_left(li,i[0])
    end = bisect.bisect_right(li,i[1])
    print(end-begin)

Solution (Python):
numq = int(input())
lis = [1]*100001
lis[0] = 0
lis[1] = 0
i = 2
while(i < 318):
  if lis[i] == 1:
    k = 2
    while(i*k < 100001):
      lis[i*k] = 0
      k += 1
  i += 1
lis2 = [0]*100001

for i in range(1,100001):
  if i % 2 == 1 and lis[i] == lis[(i+1)//2] == 1:
    lis2[i] = lis2[i-1] + 1
  else:
    lis2[i] = lis2[i-1]

for _ in range(numq):
  a,b = map(int,input().split())
  print(lis2[b] - lis2[a-1])

Solution (Python):
numq = int(input())
lis = [1]*100001
lis[0] = 0
lis[1] = 0
i = 2
while(i < 318):
  if lis[i] == 1:
    k = 2
    while(i*k < 100001):
      lis[i*k] = 0
      k += 1
  i += 1
lis2 = [0]*100001

for i in range(1,100001):
  if i % 2 == 1 and lis[i] == lis[(i+1)//2] == 1:
    lis2[i] = lis2[i-1] + 1
  else:
    lis2[i] = lis2[i-1]

for _ in range(numq):
  a,b = map(int,input().split())
  print(lis2[b] - lis2[a-1])

Solution (Python):
numq = int(input())
lis = [1]*100001
lis[0] = 0
lis[1] = 0
i = 2
while(i < 318):
  if lis[i] == 1:
    k = 2
    while(i*k < 100001):
      lis[i*k] = 0
      k += 1
  i += 1
lis2 = [0]*100001

for i in range(1,100001):
  if i % 2 == 1 and lis[i] == lis[(i+1)//2] == 1:
    lis2[i] = lis2[i-1] + 1
  else:
    lis2[i] = lis2[i-1]

for _ in range(numq):
  a,b = map(int,input().split())
  print(lis2[b] - lis2[a-1])

Solution (Python):
def primes(n):
    ass = []
    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(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

num = 10**5+10
Q = int(input())
prime_numbers = primes(num)
prime_set = set(prime_numbers)
prime_count = [0]*(num+1)
for pi in prime_numbers:
    if (pi+1)//2 in prime_set:
        prime_count[pi]+=1
for i in range(num):
    prime_count[i+1]+=prime_count[i]
for i in range(Q):
    l, r = map(int, input().split())
    print(prime_count[r]-prime_count[l-1])

Solution (Python):
import math
import sys
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ 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*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

input = sys.stdin.readline
N=10**5
prime=sieve(N)
a=[0 for i in range(N+1)]
for i in range(3,N+1):
	if prime[i] and prime[(i+1)//2]: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

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

Solution (Python):
import math
import sys
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ 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*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

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

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime

    is_prime = [True for _ 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*2, n+1, i):
                is_prime[j] = False

    return is_prime


def main():
    input = sys.stdin.readline
    Q = int(input())
    is_prime = sieve(10**5)
    A = [0 for _ in range(10**5 + 1)]
    for i in range(3, 10**5 + 1):
        if is_prime[i] and is_prime[(i+1)//2]:
            A[i] = A[i-1] + 1
        else:
            A[i] = A[i-1]

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


if __name__ == '__main__':
    main()

Solution (Python):
import math
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ 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*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

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

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

Solution (Python):
import math
def sieve(n):
    if n < 2:
        is_prime = [False for _ in range(n+1)]
        return is_prime
 
    is_prime = [True for _ 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*2, n+1, i):
                is_prime[j] = False
 
    return is_prime

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

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

Solution (Python):
import math
def Sieve_of_Eratosthenes(N):
	prime={}
	for i in range(2,N+1):
		prime[i]=1

	for i in range(2,math.ceil(N**0.5)+1):
		tmp=set()
		for j in prime:
			if j>i and j%i==0: tmp.add(j)
		for j in tmp:
			prime.pop(j)

	return prime

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

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

Solution (Python):
import math
def Sieve_of_Eratosthenes(N):
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return(prime)

N=10**5+1
s=Sieve_of_Eratosthenes(N)
a=[0]*(N)
for i in range(2,N):
	if i in s and (i+1)//2 in s: a[i]=a[i-1]+1
	else: a[i]=a[i-1]

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

Solution (Python):
import math

def main():
    max_len = 10 ** 5 + 1
    sosuu_hantei = [0 for i in range(max_len)]

    for i in range(2, max_len):
        flg = 1
        for j in range(int(i ** 0.5) + 1):
            if sosuu_hantei[j]:
                if i % j == 0:
                    flg = 0
                    break
        if flg:
            sosuu_hantei[i] = 1

    

    for i in range(max_len)[::-1]:
        if sosuu_hantei[i] == 0:
            continue
        if sosuu_hantei[(i + 1) // 2]:
            pass
        else:
            sosuu_hantei[i] = 0

    

    now_count = 0
    for i in range(max_len):
        if sosuu_hantei[i]:
            now_count += 1
        sosuu_hantei[i] = now_count

    

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


if __name__ == '__main__':
    main()

Solution (Python):

import math

def main():
    max_len = 10 ** 5 + 1
    sosuu_hantei = [0 for i in range(max_len)]

    for i in range(2, max_len):
        flg = 1
        for j in range(int(i ** 0.5) + 1):
            if sosuu_hantei[j]:
                if i % j == 0:
                    flg = 0
                    break
        if flg:
            sosuu_hantei[i] = 1

    

    for i in range(max_len)[::-1]:
        if sosuu_hantei[i] == 0:
            continue
        if sosuu_hantei[(i + 1) // 2]:
            pass
        else:
            sosuu_hantei[i] = 0

    

    now_count = 0
    for i in range(max_len):
        if sosuu_hantei[i]:
            now_count += 1
        sosuu_hantei[i] = now_count

    

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


if __name__ == '__main__':
    main()

Solution (Python):
def sieve(n): 
    num = [1]*n
    num[0]=num[1]= 0
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = 0
    return num 

primes = sieve(10**5)
like_2017 = [0]
for i in range(1,len(primes)):
    if i <= 2:
        like_2017.append(like_2017[i-1])
    elif primes[i] == 1 and primes[(i+1)//2] == 1:
        like_2017.append(like_2017[i-1]+1)
    else:
        like_2017.append(like_2017[i-1])
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r]-like_2017[l-1])

Solution (Python):
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

N = 10 ** 5 + 1
L = [1] * N

L[0] = 0
L[1] = 0

for i in range(2, N // 2):
  if L[i] == 1:
    for j in range(i * 2, N, i):
      L[j] = 0

S = [0] * N
for i in range(3, N, 2):
  S[i] = S[i - 2]
  if L[i] and L[(i + 1) // 2]:
    S[i] += 1

for l, r in lr:
  print(S[r] - S[max(l - 2, 1)])

Solution (Python):
prime = []
numberlist = []
for i in range(2, 317):
	numberlist.append(i)
while True:
	if numberlist[0] > 17:
		break
	p = numberlist.pop(0)
	newnumberlist = []
	while numberlist != []:
		now = numberlist.pop(0)
		if now%p != 0: newnumberlist.append(now)
	prime.append(p)
	numberlist = newnumberlist
for i in range(0, len(numberlist)):
	prime.append(numberlist[i])

def primejudge(n):
	if n == 1: return False
	if n in prime: return True
	for i in range(0, len(prime)):
		if n % prime[i] == 0: return False
	return True

like2017 = []
cnt = 0
for i in range(0, 100001):
	if i % 2 == 1:
		if primejudge(i) and primejudge((i+1)//2): cnt += 1
	like2017.append(cnt)

Q = int(input())
for i in range(0, Q):
	left, right = map(int, input().split())
	print(like2017[right]-like2017[left-1])

Solution (Python):
def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)]
    i=0
    p = pl[0]
    while p**2<=n:
        pl = [pl[j] for j in range(len(pl)) if pl[j]%p!=0 or j<=i]
        i+=1
        p=pl[i]
    return pl

pl=sieve_of_eratosthenes(100000)

p_list = [0 for i in range(100001)]

for p in pl:
    if 2*p-1<=100000:
        p_list[2*p-1]+=1
    p_list[p]+=1


ps_list = [0]
ps = 0

for i in range(1,100001):
    if p_list[i]>=2:
        ps+=1
    ps_list.append(ps)



Q = int(input())

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

Solution (Python):

import sys

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

def is_ok(n):
    if n % 2 == 1 and is_prime(n) and is_prime((n + 1) // 2):
        return True
    return False

def solve(Q: int, l: "List[int]", r: "List[int]"):
    N = 100000
    tmp = [0] * (N + 2)
    tmp[0] = 0
    tmp[1] = 0
    for i in range(1, N + 1):
        tmp[i + 1] = tmp[i]
        if is_ok(i):
            
            tmp[i + 1] += 1
    
    for q in range(Q):
        ret = tmp[r[q] + 1] - tmp[l[q]]
        print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    Q = int(next(tokens))  
    l = [int()] * (Q)  
    r = [int()] * (Q)  
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(Q, l, r)

if __name__ == '__main__':
    main()

Solution (Python):
import math
import bisect
def makeprime(n):
  prime = []
  for i in range(2,n+1):
    flag = 1
    for j in range(2,math.ceil(math.sqrt(i)+1)):
       if not i == 2:
                   if i%j == 0:
                    flag = 0
                    break
    if flag:
     prime.append(i)
  return prime


def solve():
  q = int(input())
  primelike = []
  primenumber = makeprime(100001)
  for i in range(100001):
    if i%2 == 0:continue
    else:
      if i in primenumber:
        if (i+1)//2 in primenumber:
          primelike.append(i)
  for j in range(q):
      l,r = (int(k) for k in input().split())
      left = bisect.bisect_left(primelike,l)
      right = bisect.bisect_right(primelike,r)
      print(right-left)
solve()

Solution (Python):
q=int(input())
l=[list(map(int,input().split())) for i in range(q)]

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

L1=primes(100000)
L2=set(L1)
like2017=[]
for i in range(len(L1)):
  if (L1[i]+1)//2 in L2:like2017.append(L1[i])
like2017=set(like2017)
ansL=[]
ct=0
for i in range(100000):
  if i in like2017:ct+=1
  ansL.append(ct)

for i in range(q):
  print(ansL[l[i][1]]-ansL[l[i][0]-1])

Solution (Python):
import math

Q = int(input())
ls = []
rs = []

for i in range(Q):
    [l, r] = input().split() 
    ls.append(int(l))
    rs.append(int(r))

rmax = max(rs)

is_prime = [1]*(rmax+1)
is_prime[0] = 0
is_prime[1] = 0

i = 1

while i < math.sqrt(rmax):
    i += 1
    if is_prime[i] == 1:
        for j in range(i*2, rmax, i):
            is_prime[j] = 0

like2017 = [0]*(rmax+1)

for i in range(1, rmax+1, 2):
    if is_prime[i] == 1 and is_prime[int((i+1)/2)] == 1:
        like2017[i] = 1
        
cumul = [0]*(rmax+1)
for i in range(1, rmax+1):
    cumul[i] = cumul[i-1] + like2017[i]

for i in range(Q):
    print(cumul[rs[i]] - cumul[ls[i]-1])

Solution (Python):
Q=int(input())
SOSU={2}
from collections import defaultdict
data=dict()
data[-1]=0
data[0]=0
data[1]=0
data[2]=0
for i in range(3,10**5+1,2):
    data[i]=data[i-2]
    flag=True
    for j in range(3,int(i**0.5)+1):
        if i%j==0:
            flag=False
            break
    if flag:
        SOSU|={i}
        if (i+1)//2 in SOSU:
            data[i]+=1
for q in range(Q):
    l,r=map(int,input().split())
    print(data[r]-data[l-2])

Solution (Python):
q=int(input())
max=100001
is_prime =[1]*max
is_prime[0] = 0
is_prime[1] = 0
for i in range(2,max):
    if not is_prime[i]:
        continue
    for j in range(i*2,max,i):
        is_prime[j] = 0

a=[0]*(max+1)
for i in range(max):
    if i%2==0:
        continue
    if is_prime[i]==1 and is_prime[(i+1)//2]:
        a[i]=1

s=[0]*(max+1)
for i in range(max):
    s[i+1]=s[i]+a[i]

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

Solution (Python):
import sys
input = sys.stdin.readline
Q = int(input())
numberlist = [0 for i in range(100001)]
prime = [2]

for i in range(3, 100001, 2):
    flag = 1
    for j in prime:
        if i % j == 0:
            flag = 0
            break
    if flag == 1:
        prime.append(i)

for i in prime:
    if (i+1)//2 in prime:
        numberlist[i] += 1
for i in range(100000):
    numberlist[i+1] += numberlist[i]


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

Solution (Python):
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50





Q = i_inpl()
l, r = [], []

max_r = -INF
for _ in range(Q):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)
    max_r = max(max_r, ri)

MAX_X = 100030
prime_table = [True] * MAX_X
prime_table[0] = prime_table[1] = False

for (i, is_prime) in enumerate(prime_table):
    if is_prime:
        for n in range(i*i, MAX_X, i):
            prime_table[n] = False


cumsums = [0]
for odd in range(3, max_r+3, 2):
    tmp = 0
    if prime_table[odd] and prime_table[(odd+1)//2]:
        tmp += 1
    cumsums.append(cumsums[-1] + tmp)

for li, ri in zip(l, r):
    if li > 1:
        li = li//2 - 1
    else:
        li = 0
    ri = ri//2
    print(cumsums[ri]-cumsums[li])

Solution (Python):
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50





Q = i_inpl()
l, r = [], []

max_r = -INF
for _ in range(Q):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)
    max_r = max(max_r, ri)

MAX_X = 100030
prime_table = [True] * MAX_X
prime_table[0] = prime_table[1] = False

for (i, is_prime) in enumerate(prime_table):
    if is_prime:
        for n in range(i*i, MAX_X, i):
            prime_table[n] = False


cumsums = [0]
for odd in range(3, max_r+3, 2):
    tmp = 0
    if prime_table[odd] and prime_table[(odd+1)//2]:
        tmp += 1
    cumsums.append(cumsums[-1] + tmp)

for li, ri in zip(l, r):
    if li > 1:
        li = li//2 - 1
    else:
        li = 0
    ri = ri//2
    print(cumsums[ri]-cumsums[li])

Solution (Python):
N = 100001
pr = [True]*(N+1)
c = [0]*(N+1)
pr[0] = pr[1] = False 
for i in range(2,N) :
    if pr[i]:
        for j in range(i+i,N,i):
            pr[j] = False

for i in range(3,N,2): 
    if pr[i] and pr[(i+1)//2]:
        c[i]+=1
for i in range(3,N):
    c[i]+=c[i-1]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(c[r]-c[l-1])

Solution (Python):
import copy
Q = int(input())
lis = []
maximam = 1
for _ in range(Q):
    l, r = map(int, input().split())
    lis.append((l, r))
    maximam = max(maximam, r)
flag_lis = [1] * (maximam+1)
flag_lis[0] = 0
flag_lis[1] = 0
for i in range(2, int((maximam-1)/2)+1):
    if flag_lis[i] != 0:
        for j in range(2*i,maximam+1,i):
            flag_lis[j] = 0
fin_lis = [0]*(maximam+1)
count = 0
for i in range(3, maximam+1, 2):
    if flag_lis[i] == 1 and flag_lis[int((i+1)/2)] == 1:
        count += 1
    fin_lis[i] = count
for (l, r) in lis:
    if l == 1:
        print(fin_lis[r] - 0)
    else:
        print(fin_lis[r] - fin_lis[l-2])