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):
from itertools import accumulate



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

    for i in range(2, n+1):
        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]]
    return is_prime, table


Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

max_R = max(R)
is_prime, table = sieve(max_R)

check = [0]*(max_R + 1)
for i in range(0, max_R + 1):
    if (i % 2 == 1):
        if (is_prime[i-1] and is_prime[(i+1)//2-1]):
            check[i] = 1


check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print(check[R[i] + 1] - check[L[i]])

Solution (Python):
def is_prime(n):
    '''
    素数判定する
    '''
    if n == 1:
        return False
    for k in range(2, int(n**0.5) + 1):
        if n % k == 0:
            return False
    return True


Q = int(input())
prime_list = [False] * 100001
L = []
R = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
a = [0] * 100001
prime_list[2] = True
for i in range(1, 100001):
    prime_list[i] = is_prime(i)
    if prime_list[i] and prime_list[(i+1)//2]:
        a[i] = a[i-1] + 1
    else:
        a[i] = a[i-1]
for i in range(Q):
    ans = a[R[i]] - a[L[i]-1]
    print(ans)

Solution (Python):
import sys 
from itertools import accumulate
input=sys.stdin.readline
Q=int(input().rstrip())
S=[list(map(int,input().rstrip().split())) for _ in range(Q)]


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

    for i in range(2, n+1):
        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]]
    is_prime=[False]+is_prime
    return is_prime, table


def resolve():
    maxN=10**5+1
    booltable1,table1=sieve(maxN)
    booltable2,table2=sieve((maxN+1)//2)
    booltable=[0 for _ in range(maxN+1)]
    for i in range(1,maxN+1,2):
        booltable[i]=booltable1[i] and booltable2[(i+1)//2]
    
    
    cumsum = list(accumulate(booltable))

    for i in range(Q):
        print(cumsum[S[i][1]]-cumsum[S[i][0]-1])
    
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):
MAXN = 10**5 + 1


f = [False] * (MAXN)
for i in range(2,MAXN):
    if not f[i]:
        for j in range(i+i,MAXN,i):
            f[j] = True
c = [0] * (MAXN)
for i in range(3,MAXN):
    if not f[i] and not f[(i+1)//2]:
        c[i] += 1
    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):
Q=int(input())
queries=[tuple(map(int,input().split())) for _ in range(Q)]


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


like2017=[0]*(10**5+1)
for i in range(1,10**5+1):
    like2017[i]=like2017[i-1]+(1 if i&1 and p[i] and p[(i+1)//2] else 0)

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

Solution (Python):
import sys
from math import floor, sqrt

def prime_nums(n):
    sieve = set(range(2, n + 1))
    non_prime = set(range(2 * 2, n + 1, 2))
    sieve -= non_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            non_prime = set(range(i * 2, n + 1, i))
            sieve -= non_prime
    return sieve

p = prime_nums(10**5)

cnt = [None] * (10**5+1)
cnt[0] = 0
for i in range(1, 10**5+1, 2):
    if i in p and (i + 1) // 2 in p:
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]
    cnt[i+1] = cnt[i]

q = int(sys.stdin.readline().rstrip())
lr = zip(*[map(int, sys.stdin.read().split())] * 2)

def main():
    for l, r in lr:
        yield cnt[r] - cnt[l-1]
    
if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Solution (Python):


import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def eratosthenes_sieve(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

MAX = 10 ** 5

primes = set(eratosthenes_sieve(MAX))
acc = [0] * (MAX+1)
for a in range(3, MAX+1, 2):
    
    if a in primes and (a + 1) // 2 in primes:
        acc[a] = 1

acc = list(accumulate(acc))

for i in range(INT()):
    l, r = MAP()
    
    ans = acc[r] - acc[l-1]
    print(ans)

Solution (Python):
import sys
from bisect import bisect, bisect_left

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def get_sieve_of_eratosthenes(n):
	prime = [2]
	limit = int(n**0.5)
	data = [i + 1 for i in range(2, n, 2)]
	append = prime.append
	while True:
		p = data[0]
		if p > limit:
			return prime + data
		append(p)
		data = [e for e in data if e % p != 0]

def main():
	primes = get_sieve_of_eratosthenes(10**5)

	prime_dict = dict(zip(primes, [1]*len(primes)))
	prime_2017 = []
	append = prime_2017.append
	for k in prime_dict.keys():
		if int((k+1)/2) in prime_dict:
			append(k)
	
	prime_2017.sort()
	

	Q = INT()
	for _ in range(Q):
		l, r = MAP()
		print(bisect(prime_2017, r)-bisect_left(prime_2017, l))

if __name__ == '__main__':
	main()

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

all=[]


def sosu(x):
  flag=True
  r=2
  while r*r<=x:
    if x%r==0:
      flag=False
      break
    r+=1
  return flag

for i in range(2,10**5+1):
  if i%2:
    if sosu(i)==True and (sosu((i+1)//2))==True:
      all.append(i)

import bisect



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

Solution (Python):

M=pow(10,5)

prime_sieve=[-1 for i in range(M+1)]
prime_sieve[0]=1
prime_sieve[1]=1

primes=[]
for i in range(M+1):
  if prime_sieve[i]==-1:
    primes.append(i)
    for j in range(2,(M)//i+1):
      prime_sieve[i*j]=1

rangesum=[0,0,0]
sum=0
for i in range(3,M+1):
  if prime_sieve[i]==-1:
    if prime_sieve[(i+1)//2]==-1:
       sum+=1
       
  rangesum.append(sum)

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

Solution (Python):
primes = set(range(3, 10**5, 2))
primes.add(2)
cumsum = [0] * (10**5 + 2)

for i in range(3, 10**5):
    if i in primes:
        for not_prime in range(i+i, 10**5, i):
            primes.discard(not_prime)


count = 0
for num in range(1, 10**5, 2):
    if num in primes:
        if (num+1)//2 in primes:
            count += 1

    cumsum[num] = count
    cumsum[num+1] = count

q = int(input())
for i in range(q):
    left, right = map(int, input().split())
    res = cumsum[right] - cumsum[left-1]
    print(res)

Solution (Python):
def prime_table(n):
  list = [True for _ in range(n + 1)]
  list[0] = False
  list[1] = False
  i = 2
  while i * i <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1
  prime_cumsum = []
  amount = 0
  for i in range(len(list)):
    if(i == 0):
      prime_cumsum.append(0)
      continue
    if(list[i] == True and (i + 1) % 2 == 0 and list[(i+1)//2] ==True):
      amount +=1
    prime_cumsum.append(amount)
  return prime_cumsum

q = int(input())
question = [list(map(int, input().split())) for _ in range(q)]
prime = prime_table(10**5+1)
for l, r in question:
  print(prime[r] - prime[l-1])

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


cumsum = [0] * (10**5 + 2)

count = 0
for num in range(1, 10**5, 2):
    if is_prime(num):
        if is_prime((num+1)//2):
            count += 1

    cumsum[num] = count
    cumsum[num+1] = count

q = int(input())
for i in range(q):
    left, right = map(int, input().split())
    res = cumsum[right] - cumsum[left-1]
    print(res)

Solution (Python):
from itertools import accumulate
import sys
input=sys.stdin.readline
def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True
def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x+1)//2):
        return True
q=int(input())
l=[0]*(10**5+1)
for i in range(1,10**5+1):
    if like2017(i):
        l[i]=1
acl = list(accumulate(l))
for i in range(q):
    l,r=map(int,input().split())
    print(acl[r]-acl[l-1])

Solution (Python):
from itertools import accumulate
def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2,int(x**0.5+1)):
        if x%i==0:
            return False
    else:
        return True
def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x+1)//2):
        return True
q=int(input())
l=[0]*(10**5+1)
for i in range(1,10**5+1):
    if like2017(i):
        l[i]=1
acl = list(accumulate(l))
for i in range(q):
    l,r=map(int,input().split())
    print(acl[r]-acl[l-1])

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

sl = 10**5 + 1

s = [i % 2 for i in range(sl)]
s[0] = s[1] = 0
s[2] = 1

for i in range(2, sl):
  if s[i] == 0: continue
  for j in range(2 * i, sl, i):
    s[j] = 0

dp = [0] * sl
for i in range(3, sl):
  dp[i] = dp[i-1] + (s[i] and s[(i+1)//2])

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

Solution (Python):

MAX = 10**5+1

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

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

likes = [0] * (MAX+1)
for i in range(0, MAX+1):
    if i % 2 == 0: continue
    if is_prime[i] and is_prime[(i+1)//2]:
        likes[i] = 1
    
c = [0] * (MAX+1)
for i in range(MAX):
    c[i+1] = c[i] + likes[i]

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

for i in range(Q):
    print(c[lr[i][1]+1] - c[lr[i][0]])

Solution (Python):
def d_2017_like_number():
    Q = int(input())
    I = [[int(i) for i in input().split()] for j in range(Q)]

    def prime_table(n):
        """n 以下の整数がそれぞれ素数かどうかのリスト (エラトステネスの篩)"""
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False  
        for j in range(2, int(n**0.5) + 1):
            if not is_prime[j]:
                continue
            for k in range(j * 2, n + 1, j):
                is_prime[k] = False  
        return is_prime

    def calc_like2017(m, p):
        
        
        c = [0] * (m + 1)  
        for i in range(3, m + 1, 2):  
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, m + 1):
            c[i] += c[i - 1]
        return c

    like2017 = calc_like2017(10**5, prime_table(10**5))
    ans = [like2017[r] - like2017[l - 1] for l, r in I]
    return '\n'.join(map(str, ans))

print(d_2017_like_number())

Solution (Python):
import bisect,sys
from itertools import accumulate
input = sys.stdin.readline
def prime(n):
  prime_table = [2]
  for i in range(3,n+1):
    f = 1
    for j in prime_table[:bisect.bisect_right(prime_table,int(i**0.5))]:
      if i % j == 0:
        f = 0
        break
    if f:
      prime_table.append(i)
  return prime_table

q = int(input())
prime_table = prime(10**5)
like_2017 = [0]*(10**5+1)
for i in range(1,10**5+1,2):
  if i in prime_table and (i+1) //2 in prime_table:
    like_2017[i] = 1
like_2017 = list(accumulate(like_2017))
for i in range(q):
  l,r = map(int,input().split())
  print(like_2017[r] - like_2017[l-1])

Solution (Python):
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
p = [2]
res = [0] * (pow(10, 5) + 1)
for i in range(3, pow(10, 5), 2):
  f = 0
  for x in p:
    if i % x == 0:
      f = 1
      break
  if f == 0: p.append(i)
ps = set(p)
for i in range(3, len(res) - 1):
  if i % 2 == 0: res[i] = res[i - 1]
  x = (i in ps) and (((i + 1) // 2) in ps)
  res[i] = res[i - 1] + x

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

Solution (Python):
import math
q = int(input())
scope = [tuple(map(int, input().split())) for _ in range(q)]
prime_flag = [True] * (10 ** 5 + 1)
prime_flag[0] = False
prime_flag[1] = False
prime_cnt = [0] * (10 ** 5 + 1)

for i in range(2, math.ceil(math.sqrt(10 ** 5))):
    for j in range(i + i, 10 ** 5 + 1, i):
        prime_flag[j] = False


for i in range(2, 10 ** 5 + 1):
    prime_cnt[i] = prime_cnt[i - 1]
    num = (i + 1) / 2
    if num % 1 == 0 and prime_flag[i] and prime_flag[int(num)]:
        prime_cnt[i] += 1

for i in range(q):
    left = scope[i][0]
    right = scope[i][1]
    print(prime_cnt[right] - prime_cnt[left - 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())
scope = [tuple(map(int, input().split())) for _ in range(q)]
prime_cnt = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    prime_cnt[i] = prime_cnt[i - 1]
    if ((i + 1) / 2) % 1 == 0 and is_prime(i) and is_prime((i + 1) / 2):
        prime_cnt[i] += 1

for i in range(q):
    left = scope[i][0]
    right = scope[i][1]
    print(prime_cnt[right] - prime_cnt[left - 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())
scope = [tuple(map(int, input().split())) for _ in range(q)]
prime_cnt = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    prime_cnt[i] = prime_cnt[i - 1]
    if ((i + 1) / 2) % 1 == 0 and is_prime(i) and is_prime((i + 1) / 2):
        prime_cnt[i] += 1

for i in range(q):
    left = scope[i][0]
    right = scope[i][1]
    print(prime_cnt[right] - prime_cnt[left - 1])

Solution (Python):
def main():
    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())
    scope = [tuple(map(int, input().split())) for _ in range(q)]
    prime_cnt = [0] * (10 ** 5 + 1)
    for i in range(1, 10 ** 5 + 1):
        prime_cnt[i] = prime_cnt[i - 1]
        if ((i + 1) / 2) % 1 == 0 and is_prime(i) and is_prime((i + 1) / 2):
            prime_cnt[i] += 1

    for i in range(q):
        left = scope[i][0]
        right = scope[i][1]
        print(prime_cnt[right] - prime_cnt[left - 1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
Q = int(input())
P = 10 ** 5
c1 = [i % 2 == 1 for i in range(P)]
c2 = [False for i in range(P)]
c1[2] = True
c2[3] = True
L = deque([])
for i in range(2, P):
    if c1[i]:
        ind = i*2-1
        if ind < P:
            c2[ind] = True
        ind = i * 2
        while ind < P:
            c1[ind] = False
            ind += i
    if c1[i] and c2[i]:
        L.append(i)

for q in range(Q):
    l, r = [int(x) for x in input().strip().split()]
    print(bisect_right(L, r) -  bisect_left(L, l))

Solution (Python):
C=[0]*(10**5+2)
C[0]=1
C[1]=1
s=[0]*(10**5+2)
S=[0]*(10**5+2)
t=1
while(t<=(10**5)):
    t+=1
    if(C[t]==1):
        continue
    k=1
    while(True):
        k+=1
        if(t*k>(10**5)):
            break 
        C[t*k]=1

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

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

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

Solution (Python):
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    
    return is_prime
n=10**5+2
a=sieve(n)
ans=[0]*(n//2)
for i in range(0,n,2):
    if a[i] and a[i//2]:
        ans[i//2]=1

for i in range(1,n//2):
    ans[i]+=ans[i-1]

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

Solution (Python):
import math
import bisect
def seachPrimeNum(N):
    max = int(math.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

L=seachPrimeNum(10**5)
L=[i for i in L if (i+1)//2 in L]
Q=int(input())
for _ in range(Q):
    l,r=map(int,input().split())
    print(bisect.bisect_right(L,r) - bisect.bisect_left(L,l))

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


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

cum_like2017 = [0] * (N+1)
for i in range(1,N+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        cum_like2017[i] = cum_like2017[i-1] + 1
    else:
        cum_like2017[i] = cum_like2017[i-1] 


for l, r in lr:
    print(cum_like2017[r] - cum_like2017[l-1])

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

max_val = max([lr[1] for lr in lr_list])


num_list = list(range(max_val + 1))
for num in num_list[2:max_val // 2 + 1]:
    if num > 0:
        for i in range(num*2, max_val+1, num):
            num_list[i] = -1

prime_num_set = set([num for num in num_list if num>0][1:])


sum_list = [0, 0, 0]
for i in range(3, max_val+1):
    if i in prime_num_set and (i+1)//2 in prime_num_set:
        sum_list.append(sum_list[-1]+1)
    else:
        sum_list.append(sum_list[-1])

for l, r in lr_list:
    print(sum_list[r] - sum_list[l-1])

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

max_val = max([lr[1] for lr in lr_list])


num_list = list(range(max_val + 1))
for num in num_list[2:max_val // 2 + 1]:
    if num > 0:
        for i in range(num*2, max_val+1, num):
            num_list[i] = -1

prime_num_set = set([num for num in num_list if num>0][1:])


sum_list = [0, 0, 0]
for i in range(3, max_val+1):
    if i in prime_num_set and (i+1)//2 in prime_num_set:
        sum_list.append(sum_list[-1]+1)
    else:
        sum_list.append(sum_list[-1])

for l, r in lr_list:
    print(sum_list[r] - sum_list[l-1])

Solution (Python):
q = int(input())
F = [1]*(10**5)
for i in range(2,5*10**4):
    F[i*2]=0

F[1]=0
for i in range(3,350,2):
    for n in range(3,10**5,2):
        if n>i and n%i==0:
            F[n]=0

acc = 0
L =[0]
for i in range(1,10**5):
    if F[i] and F[(i+1)//2]:
        acc+=1
    L.append(acc)
L.append(0)

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

Solution (Python):
import math

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


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

can = primes(10**5)
like_2017 = []

for m in can:
    limit = (max(can)//2)
    if m > limit :
        break
    if 2*m-1 in can:
        like_2017.append(2*m-1)

count = 0
can_count = []
for i in range(10**5):
    if i in like_2017:
        count += 1
    else:
        pass
    can_count.append(count)

for pair in l_r:
    l = pair[0]
    r = pair[1]
    ans = can_count[r] - can_count[l-1]
    print(ans)

Solution (Python):
import math

def Sieve_of_Eratosthenes(n):
    if n < 2:
        raise ValueError('n is more than 2.')
    prime = []
    limit = math.sqrt(n)
    can = [i for i in range(2, n+1)]
    while True:
        p = can[0]
        if limit <= p:
            return prime + can
        prime.append(p)
        can = [x for x in can if x%p != 0]

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

can = Sieve_of_Eratosthenes(10**5)
like_2017 = []

for m in can:
    limit = (max(can)//2)
    if m > limit :
        break
    if 2*m-1 in can:
        like_2017.append(2*m-1)

count = 0
can_count = []
for i in range(10**5):
    if i in like_2017:
        count += 1
    else:
        pass
    can_count.append(count)

for pair in l_r:
    l = pair[0]
    r = pair[1]
    ans = can_count[r] - can_count[l-1]
    print(ans)

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):

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd



def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)



show_flg = False



def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return is_prime


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q

    for i in range(Q):
        l[i], r[i] = MI()

    prime_list = primes(10**5+1)
    arr = []
    for i in range(10**5+1):
        if i % 2 == 1:
            arr.append(int(prime_list[i] and prime_list[(i+1)//2]))
        else:
            arr.append(0)
    ARR = list(accumulate([0] + arr))

    for i in range(Q):
        
        
        print(ARR[r[i]+1] - ARR[l[i]])


if __name__ == '__main__':
    main()

Solution (Python):

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd



def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)



show_flg = False



def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return is_prime


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q

    for i in range(Q):
        l[i], r[i] = MI()

    prime_list = primes(10**5+1)
    arr = []
    for i in range(10**5+1):
        if i % 2 == 1:
            arr.append(int(prime_list[i] and prime_list[(i+1)//2]))
        else:
            arr.append(0)
    ARR = list(accumulate([0] + arr))

    for i in range(Q):
        
        
        print(ARR[r[i]+1] - ARR[l[i]])


if __name__ == '__main__':
    main()

Solution (Python):

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd



def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)



show_flg = False


def is_prime(n):
    """
    nの素数判定
    :param int n:
    :rtype: Bool
    """
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    Q = I()
    l = [0] * Q
    r = [0] * Q

    for i in range(Q):
        l[i], r[i] = MI()

    arr = []
    for i in range(10**5+1):
        if i % 2 == 1:
            arr.append(int(is_prime(i) and is_prime((i+1)//2)))
        else:
            arr.append(0)

    ARR = list(accumulate([0] + arr))
    
    

    for i in range(Q):
        
        
        print(ARR[r[i]+1] - ARR[l[i]])


if __name__ == '__main__':
    main()

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

def init_prime(n_max :int):
    """ https://qiita.com/fantm21/items/5e270dce9f4f1d963c1e
    
    """
    if n_max <= 1: return []
    if n_max == 2: return [2,]
    prime = [2,]
    _app_p = prime.append
    limit = int(n_max**0.5)
    data = [i for i in range(3, n_max+1, 2)]
    while data:
        p = data[0]
        if p > limit:
            return prime + data
        _app_p(p)
        data = [e for e in data if e%p]

def main():
    N = 10**5
    vP = init_prime(N)
    sP = set(vP)

    vA = [0,]
    appA = vA.append
    cnt = 0
    for i in range(1, N+1):
        if i in sP and (i+1)//2 in sP:
            cnt += 1
        appA(cnt)

    

    Q = int(input())
    vRes = []
    appRes = vRes.append
    for _ in range(Q):
        L, R = map(int, input().split())
        appRes(vA[R] - vA[L-1])
    print(*vRes, sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):
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
S=[]
for i in range(1,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    S+=[i]
Count=[0]
count=0
for i in range(1,10**5):
  if i in S:
    count+=1
  Count +=[count]

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

Solution (Python):
import sys
from itertools import accumulate
q = int(input())
ls = []

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 is_prime

pr = primes(10 ** 5)
pr = [j and pr[i*2-1] for i, j in enumerate(pr[:5*10**4+1])]
new_pr = [i for i in accumulate(pr)]

for i in range(q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    print(new_pr[(r+1)//2] - new_pr[(l-1)//2])

Solution (Python):
from itertools import accumulate

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


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

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




if __name__ == "__main__":
    main()