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 sys
try:
    from typing import List
except ImportError:
    pass


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


def solve(Q: int, l: "List[int]", r: "List[int]"):
    pm = [is_prime(n) for n in range(1, 100001, 2)]
    tm = [
        pm[(n - 1) // 2] and (
            n == 3 or
            ((n + 1) // 2 % 2 == 1 and pm[((n + 1) // 2 - 1) // 2])
        )
        for n in range(1, 100001, 2)
    ]
    acc = [0] * (len(tm) + 1)
    for i in range(len(tm)):
        acc[i + 1] = acc[i] + int(tm[i])
    for li, ri in zip(l, r):
        print(acc[(ri - 1) // 2 + 1] - acc[(li - 1) // 2])


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 itertools
n = int(input())
lr = [[int(i) for i in input().split()] for _ in range(n)]
m = 101010
p = [1]*m
p[0] = p[1] = 0
for i in range(2, m):
    if p[i] == 0: continue
    else:
        for j in range(2*i, m, i):
            p[j] = 0
a = [0]*m
for i in range(1, m, 2):
    if p[i] == p[(i+1)//2] == 1: a[i] = 1
a = list(itertools.accumulate(a))
for l, r in lr:
    print(a[r] - a[l-1])

Solution (Python):
import math

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

prime=[]
for n in range(2, 10**5+1):
    for i in range(2, math.floor(math.sqrt(n)) + 1):
        if n % i == 0:
            break
    else:
        prime.append(n)




like2017=[0]*(10**5+1)
for p in prime:
    if (p+1)//2 in prime:
        like2017[p]=1


cumulative=[0]
for i in range(10**5):
    cumulative.append(like2017[i]+cumulative[i])


for q in lr:
    l, r = q
    print(cumulative[r+1]-cumulative[l])

Solution (Python):
import numpy as np

Q = int(input())
q = list()
n = 10 ** 5 + 1
for _ in range(Q):
    l, r = map(int, input().split())
    q.append((l, r))


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

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

ans = np.cumsum(N)
for l, r in q:
    print(ans[r] - ans[l - 1])

Solution (Python):
MAX = 101010
Prime = [1] * MAX
Prime[0] = 0
Prime[1] = 0
for i in range(2, MAX):
    if not Prime[i]:
        continue
    for j in range(i*2, MAX, i):
        Prime[j] = 0

Like = [0] * MAX
for i in range(MAX):
    if Prime[i] and Prime[(i+1)//2]:
        Like[i] = 1

Sum = [0] * (MAX + 1)
for i in range(MAX):
    Sum[i+1] = Sum[i] + Like[i]

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

q = int(input())

def eratosthenes2(limit):
    is_prime = [1] * (limit + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]==0:
            continue
        for j in range(i * 2, limit + 1, i):
            is_prime[j] = 0
    return is_prime

limit = 10**5

is_prime = eratosthenes2(limit)
prime_list = [i for i in range(limit + 1) if is_prime[i]]

like_2017=[0]*limit

for p in prime_list:
    if is_prime[(p+1)//2]==1:
        like_2017[p] = 1

from itertools import accumulate
B = [0] + like_2017
B = list(accumulate(B))

ans=[0]*q
for i in range(q):
    l, r = map(int, input().split())
    ans[i]=B[r+1]-B[l]

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

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

    def get_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[i] for i in range(n + 1)]

    primes = get_primes(10**5+1)
    cum = [0] * (10**5 + 1)
    for i in range(2, 10**5+1):
        cum[i] += cum[i-1]
        if i % 2 and primes[i] and primes[(i+1)//2]:
            cum[i] += 1
    for _ in range(Q):
        l, r = map(int, input().split())
        print(cum[r] - cum[l-1])
resolve()

Solution (Python):

import sys
input = sys.stdin.readline




N = 100010
primes = []
is_prime = [True]*N
for i in range(2,N):
    if is_prime[i]:
        primes.append(i)
        j = 2
        while i*j < N:
            is_prime[i*j] = False
            j += 1






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


Ans = [0]*N
for p in primes:
    if p==2:
        continue
    
    if (p+1)//2 in primes:
        Ans[p] = 1


for i in range(1,N):
    Ans[i] += Ans[i-1]


for l,r in LR:
    print(Ans[r] - Ans[l-1])

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


def IsPrime(x):
    if x == 2:
        return True
    elif x % 2 == 0:
        return False
    else:
        for i in range(3, int(x**0.5)+2, 2):
            if x%i == 0:
                return False
        else:
            return True
        

like = [False] * (10**5+1)
for i in range(3, 10**5, 2):
    like[i] = IsPrime(i) and IsPrime((i+1)//2)

ans = [0]*(10**5+1)
tmp = 0
for i in range(10**5+1):
    if like[i] == True:
        tmp += 1
    ans[i] = tmp

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

Solution (Python):

import math

def submit():
    n_max = 10**5

    
    is_prime = {x: True for x in range(1, n_max + 1)}
    is_prime[1] = False
    for x in range(2, math.ceil(math.sqrt(n_max)) + 1):
        if is_prime[x]:
            y = 2 * x
            while y <= n_max:
                is_prime[y] = False
                y += x

    like2017 = {}
    for x in range(1, n_max + 1):
        like2017[x] = x % 2 and is_prime[x] and is_prime[(x + 1) // 2]

    
    accumulation = {0: 0}
    for x in range(1, n_max + 1):
        accumulation[x] = accumulation[x - 1] + like2017[x]
    
    
    q = int(input())
    queries = []
    for _ in range(q):
        queries.append(list(map(int, input().split())))
        
    for l, r in queries:
        print(accumulation[r] - accumulation[l - 1])
    
submit()

Solution (Python):
q=int(input())
s=set()
arr=[0]*(10**5+1)
for i in range(2,10**5+1):
  if arr[i]==0:
    s.add(i)
    for j in range(i,10**5+1,i):
      arr[j]+=1
cnt=[0]*(10**5+1)
for i in range(10**5+1):
  if i in s and (i+1)//2 in s:
    cnt[i]=1
for i in range(10**5):
  cnt[i+1]+=cnt[i]
for _ in range(q):
  l,r=map(int,input().split())
  print(cnt[r]-cnt[l-1])

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
b = [0,0,0]
def judge(n):
    if  n!= 1 and all(n%i != 0 for i in range(2,round(n**(1/2) +1))):
        return True
    else:
        return False
for i in range(3,10**5):
    if judge(i) and judge((i+1)/2):
        b.append(1)
    else:
        b.append(0)
cnt = [0]*(10**5)
for i in range(1,10**5):
    cnt[i] = cnt[i-1] + b[i]
for i in range(n):
    ans = cnt[a[i][1]] - cnt[a[i][0]-1]
    print(ans)

Solution (Python):
Q=int(input())
prime = [1]*(10**5+1)
prime[0],prime[1]=0,0
for i in range(2,int(pow(10**5,0.5)+3)):
    if not prime[i]:
        continue
    for j in range(i*2,10**5+1,i):
        prime[j]=0
near_2017 = [1]*(10**5+1)
near_2017[0:3]=[0,0,0]
for i in range(3,10**5+1):
    if prime[i] and prime[(i+1)//2]:
        near_2017[i]=near_2017[i-1]+1
    else:
        near_2017[i]=near_2017[i-1]
for i in range(Q):
    l,r=map(int,input().split(' '))
    print(near_2017[r]-near_2017[l-1])

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

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

p = era(10**5+100)
s = set(p)
is_like = [0]*(10**5+100)

for i in range(len(is_like)):
    if i in s and (i+1)//2 in s:
        is_like[i] = 1

acc = [0]

for i in range(len(is_like)):
    acc.append(acc[-1]+is_like[i])

Q = int(input())

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

Solution (Python):
q = int(input())
n = 10**5+1
p = [0]*n
p[2] = 1
for i in range(3,10**5+1):
  prime = 1
  for j in range(2, int(i**0.5)+1):
    if i%j==0:
      prime = 0
      break
  if prime:
    p[i] = 1

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

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

Solution (Python):


import sys

def main():
    is_prime = sieve(10 ** 5 + 1)
    is_like2017 = [(is_prime[i] and is_prime[(i + 1) // 2]) for i in range(10 ** 5 + 1)]
    counter = [0]
    for i in range(1, 10 ** 5 + 1):
        counter.append(counter[-1] + (1 if is_like2017[i] else 0))

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



def sieve(n):  
    s = [True] * n
    s[0] = s[1] = False
    for x in range(2, int(n**0.5) + 1):
        if s[x]:
            for i in range(2 * x, n, x):
                s[i] = False
    return s

if __name__ == "__main__":
    main()

Solution (Python):


def main():
    is_prime = sieve(10 ** 5 + 1)
    is_like2017 = [(is_prime[i] and is_prime[(i + 1) // 2]) for i in range(10 ** 5 + 1)]
    counter = [0]
    for i in range(1, 10 ** 5 + 1):
        counter.append(counter[-1] + (1 if is_like2017[i] else 0))

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



def sieve(n):  
    s = [True] * n
    s[0] = s[1] = False
    for x in range(2, int(n**0.5) + 1):
        if s[x]:
            for i in range(2 * x, n, x):
                s[i] = False
    return s

if __name__ == "__main__":
    main()

Solution (Python):



counts = []
counts.append(0)
counts.append(0)
counts.append(0)

prime = []

is_prime = []
is_prime.append(False)
is_prime.append(False)

def sieve(r):
    for i in range(2, r + 1):
        is_prime.append(True)

    for i in range(2, r + 1):
        if is_prime[i]:
            prime.append(i)

            j = 2 * i
            while j <= r:
                is_prime[j] = False
                j = j + i

def calc_like_number_count(r):
    for i in range(3, r + 1):
        if i % 2 == 1 and is_prime[i] and is_prime[(i + 1) // 2]:
            counts.append(1)
        else:
            counts.append(0)
    
    for i in range(3, r + 1):
        counts[i] = counts[i] + counts[i - 1]


def main():
    Q = int(input())
    querys = []
    max_r = 0
    for i in range(Q):
        l, r = map(int, input().split())
        querys.append((l, r))
        if max_r < r:
            max_r = r

    sieve(max_r)
    calc_like_number_count(max_r)

    for l, r in querys:
        print(counts[r] - counts[l - 1])
    
main()

Solution (Python):
import math
def using_sqrt(limit):
    n = 0
    primes = set()
    for k in range(2, limit+1):
        factor = 0
        
        
        if k % 2 == 0 and k != 2:
            continue
        
        
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1
                
        if factor == 0:
            primes.add(k)
            
    return primes

primes = using_sqrt(10**5+1)

likely = []
count = 0
for i in range(10**5+1):
    if i in primes and (i+1)/2 in primes:
        count += 1
    likely.append(count)
        
q = int(input())
    
for i in range(q):
    l, r = map(int,input().split())
    print(likely[r]-likely[l-1])

Solution (Python):
import math
Q = int(input())
rui = [0]*50000
def sosuu(n):
    for i in range(2,1+int(math.sqrt(n))):
        if n % i == 0:
            return 0
    return 1
for i in range(1,50000):
    n = i*2 + 1
    han = 0
    rui[i] = rui[i-1] + min(sosuu(n),sosuu((n+1)/2))
for i in range(Q):
    l,r = [int(x) for x in input().split()]
    l2 = (l-1) // 2
    r2 = (r-1) // 2
    if l2 != 0:
        print(rui[r2] - rui [l2-1])
    else:
        print(rui[r2])

Solution (Python):
from math import ceil, sqrt
from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def eratosthenes(n):
    p = []         
    t = [-1] * n   
    t[0] = 0
    t[1] = 0

    for i in range(2, ceil(sqrt(n))):
        if t[i] == -1:
            p.append(i)
            
            for j in range(2*i, n, i):
                if t[j] == -1:
                    t[j] = i
 
    for j in range(i+1, n):
        if t[j] == -1:
            p.append(j)
            
 
    return p, t
 

def main():
    Q,*lr = map(int, read().split())

    P, T = eratosthenes(10**5+5)
    table2017 = [0] * (10**5+5)
    for p in P:
        if T[(p+1)//2] == -1:
            table2017[p] = 1
    acc = list(accumulate(table2017))

    for l, r in zip(*[iter(lr)]*2):
        print(acc[r] - acc[l-1])


if __name__ == "__main__":
    main()

Solution (Python):
size = 10 ** 5
is_prime = [True] * size
is_prime[0] = False
for i in range(1, int(size ** 0.5)):
  if not is_prime[i]:
    continue
  for j in range(2 * i + 1, size, i + 1):
    is_prime[j] = False
counts = [0] * size
for i in range(size):
  if is_prime[i] and is_prime[(i + 1) // 2]:
    counts[i] = counts[i - 1] + 1
  else:
    counts[i] = counts[i - 1]

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

Solution (Python):

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

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

m = 0
for l, r in lr:
    m = max(l, r, m)
prime_count = [0, 0]
for i in range(2, m+1):
    prime_count += [is_prime(i)]
similar = [0]*(m+1)
for i in range(3, m+1):
    if prime_count[i] == 1 and prime_count[(i+1)//2] == 1:
        similar[i] = 1
for i in range(m):
    similar[i+1] = similar[i+1] + similar[i]

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

Solution (Python):
def sieve(N):
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime

lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
lis = set(lis)-{0}
c = [0]*(10**5+1)
for i in range(10**5):
    if i+1 in lis:
        c[i+1] = c[i]+1
    else:
        c[i+1] =c[i]
c = tuple(c)
for _ in range(Q):
    l,r = map(int,input().split())
    tmp = c[r]-c[l-1]
    print(tmp)

Solution (Python):
def sieve(N):
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    return prime
from bisect import bisect_left as bl
from bisect import bisect_right as br
lis = sieve(10**5)
prime = set(lis)-{0}
for i in range(len(lis)):
    if lis[i] != 0:
        if (lis[i]+1)//2 in prime:continue
        else:lis[i] = 0
    else:continue
Q = int(input())
lis = set(lis)-{0}
lis = sorted(tuple(lis))
for _ in range(Q):
    l,r = map(int,input().split())
    t = bl(lis,l)
    s = br(lis,r)
    tmp = s-t
    print(tmp)

Solution (Python):
from itertools import accumulate

def get_prime_number_list(N):
    
    primes = [2]
    limit = int(N**0.5)
    data = [i+1 for i in range(2, N, 2)]
    while 1:
        p = data[0]
        if limit <= p:
            return primes + data
        primes.append(p)
        data = [e for e in data if e%p != 0]

def main():
    Q=int(input())
    primes = get_prime_number_list(10**5)
    prime_lst = [0]*(10**5+10)
    tmp = [0]*(10**5+10)
    for prime in primes:
        prime_lst[prime] = 1
    for i in range(3, 10**5+10, 2):
        if prime_lst[i] and prime_lst[(i+1)//2]:
            tmp[i] = 1
    ans = list(accumulate(tmp))
    l_r = []
    for _ in range(Q):
        l_r.append(map(int,input().split()))
    for l,r in l_r:
        print(ans[r] - ans[l-1])

main()

Solution (Python):
import math

def sieve(n):
    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 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

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

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print(c[r]-c[l-1])

Solution (Python):
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 set([i for i in range(n + 1) if is_prime[i]])
 
p_set = primes(10 ** 5)
sum_list = [0] * ((10 ** 5) + 1)
 
for i in range(len(sum_list) - 1):
    ret = 0
    if (i+1) in p_set and ((i+2) // 2) in p_set:
        ret = 1
    else:
        ret = 0
    sum_list[i+1] = sum_list[i] + ret

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

Solution (Python):
lim = 10 ** 5

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

like = [False] * (lim + 1)
for i in range(1, lim + 1):
    if primes[i] and primes[(i + 1) // 2]:
        like[i] = True

cumsum = [0] * (lim + 1)
for i in range(1, lim + 1):
    if like[i]:
        cumsum[i] = cumsum[i - 1] + 1
    else:
        cumsum[i] = cumsum[i - 1]

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

Solution (Python):
from bisect import bisect, bisect_left


size = 10 ** 5 + 1

is_prime = [True] * size
is_prime[0] = is_prime[1] = False


for i in range(2, 317):
  j = 2 * i
  while j < size:
    is_prime[j] = False
    j += i


like_numbers = [
  i 
  for i, x in enumerate(is_prime)
  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]

Q = int(input())

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

Solution (Python):
from bisect import bisect, bisect_left


size = 10 ** 5 + 1

is_prime = [True] * size
is_prime[0] = is_prime[1] = False


for i in range(2, 317):
  j = 2 * i
  while j < size:
    is_prime[j] = False
    j += i

like_numbers = [
  i 
  for i, x in enumerate(is_prime)
  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]

Q = int(input())



for _ in range(Q):
  l, r = map(int, input().split())
  if l == r:
    print(1 if l in like_numbers else 0)
  else:
  	print(bisect(like_numbers, r) - bisect_left(like_numbers, l))

Solution (Python):
thres = 10 ** 5

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

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

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

q = int(input())

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

Solution (Python):
def check(i):
    num=int(i**0.5)
    if i==1:return 0
    if i==2:return 1
    for j in range(2,num+1):
        if i%j==0:break

    else:return 1
    return 0
q=int(input())
lr=[list(map(int,input().split())) for i in range(q)]

L=[0]*(10**5+1)
for i in range(10**5+1):
    if i%2==0:
        L[i]=L[i-1]
    else:
        L[i]=L[i-1]+check(i)*check((i+1)//2)

for l,r in lr:
    cnt=L[r]-L[l-1]
    print(cnt)

Solution (Python):
import math

q=int(input())
N=[0]*(10**5+1)
N[3]=1
N[2]=1
S=[]

for i in range(5,10**5+1,2):
    flag=True
    for j in range(3,int(math.sqrt(i))+1,2):
        if i%j==0:
            flag=False
            break
    if flag:
        N[i]=1

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

Solution (Python):
import math

q=int(input())
N=[0]*(10**5+1)
N[3]=1
N[2]=1
S=[]

for i in range(5,10**5+1,2):
    flag=True
    for j in range(3,int(math.sqrt(i))+1,2):
        if i%j==0:
            flag=False
            break
    if flag:
        N[i]=1

X=[0]*(10**5+1)
X[2]=1
cnt=0
for i in range(3,10**5+1,2):
    if N[i]==1 and N[(i+1)//2]==1:
        cnt+=1
    X[i]=cnt
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    Q.append([l,r])

for l,r in Q:
    print(X[r]-X[l-2])

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())
lr = []
rmax = 0
for _ in range(q):
    l, r = map(int, input().split())
    lr.append([l, r])
    rmax = max(rmax, r)

csum = [0]
for i in range(1, rmax+1):
    if is_prime(i) and (i+1) % 2 == 0 and is_prime((i+1)//2):
        csum.append(csum[i-1]+1)
    else:
        csum.append(csum[i-1])


for i in range(q):
    if lr[i][1] == lr[i][0]:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])
        
    else:
        print(csum[lr[i][1]]-csum[lr[i][0]-1])

Solution (Python):
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
n=int(input())
prime=primes((10**5)+1)
memo=[0]*((10**5)+1)

for i in range(1,(10**5)+1,2):
    if prime[i]==True and prime[(i+1)//2]==True:
        memo[i]=1
      
from itertools import accumulate  
ac=list(accumulate(memo))


for i in range(n):
    l,r=map(int,input().split())
    if l!=0:
        print(ac[r]-ac[l-1])
    elif l==0:
        print(ac[r])

Solution (Python):
N = 10**5
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
ans = [0 for _ in range(N+10)]

def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x%2 == 0:
        return False
    for i in range(3, min(int(x**0.5)+5, x), 2):
        if x%i == 0:
            return False
    return True

for i in range(1, len(ans)):
    if is_prime(i) and is_prime((i+1)//2):
        ans[i] += 1
    ans[i] += ans[i-1]

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

Solution (Python):
import sys


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

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

    return is_prime


N = 10 ** 5
isPrime = sieve(N)
is2017 = [0] * (N + 1)
for i in range(N + 1):
    if 2 * i - 1 <= N and isPrime[i] and isPrime[2 * i - 1]:
        is2017[2 * i - 1] = 1

S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + is2017[i + 1]

Q = int(input())
for s in sys.stdin.readlines():
    l, r = map(int, s.split())
    print(S[r] - S[l - 1])

Solution (Python):
N = int(input())
A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int, input().split())
  
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

P,Q = [0]*10**5,[0]*10**5
P[2]=True
Q[1]=0
for i in range(3,10**5,2):
  P[i] = is_prime(i)
  if P[i]==True and P[(i+1)//2]==True:
    Q[i]=Q[i-2]+1
  else:
    Q[i]=Q[i-2]
    
ans = []
for i in range(N):
  if A[i]==1:
    ans.append(Q[B[i]])
  else:
    ans.append(Q[B[i]]-Q[A[i]-2])

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

Solution (Python):

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 i in range(q):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)

p = primes(max(r))
cnt = [0 for i in range(max(r)+1)]
for i in p:
    if (i + 1) // 2 in p:
        cnt[i]+=1

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

for i in range(q):
    print(cnt[r[i]] - cnt[l[i] - 1])

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 

q = int(input())
lr = []
minimum = float('inf')
maximum = 0
for _ in range(q):
    l, r = map(int, input().split())
    minimum = min(minimum, l)
    maximum = max(maximum, r)
    lr += [[l, r]]

prime = {i: 0 for i in range(1, maximum+1)}

for i in range(1, maximum+1):
    if is_prime(i) and is_prime((i+1)//2):
        prime[i] = 1

cum_prime = {i: 0 for i in range(1, maximum+1)}
cum_prime[minimum] = prime[minimum]
for i in range(1, maximum):
    cum_prime[i+1] = prime[i+1] + cum_prime[i]

cum_prime[0] = 0
for l, r in lr:
    print(cum_prime[r]-cum_prime[l-1])

Solution (Python):
import sys 

input = sys.stdin.readline


q = int(input())
qry = [None] * q


mn = 10 ** 5
mx = 0
for i in range(q):
    qry[i] = list(map(int, input().split()))
    if qry[i][0] < mn:
        mn = qry[i][0]
    if qry[i][1] > mx:
        mx = qry[i][1]

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


cum = [0] * (mx + 1)
cum[0] = 0

for i in range(1, len(cum)):
    d = 0
    if i % 2 == 0:
        d = 0
    if is_prime(i) and is_prime((i + 1) // 2):
        d = 1
    cum[i] = cum[i - 1] + d

for i in range(q):
    print(cum[qry[i][1]] - cum[qry[i][0] - 1])

Solution (Python):
d = [0]
ans = 0

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

Q = int(input())

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

Solution (Python):
q=int(input())
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
p=primes(10**5)
accum=[0]*(10**5+1)
s=set(p)
for i in range(1,10**5+1):
  if i%2:
    if i in s and (i+1)//2 in s:
      accum[i]+=1
for i in range(10**5):
  accum[i+1]+=accum[i]
for _ in range(q):
  l,r=map(int,input().split())
  if l==1:
    print(accum[r])
  else:
    print(accum[r]-accum[l-1])

Solution (Python):
def erat(n):
    l = [0, 0] + [1 for _ in range(n - 1)]
    i = 2
    while (i < n + 1):
        if l[i] == 1:
            for j in range(i**2, n + 1, i):
                l[j] = 0
        i += 1

    return l


n_max = 10**5
is_prime = erat(n_max)
is_2017 = [0 for _ in range(n_max + 1)]
for i in range(2, n_max + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        is_2017[i] = 1

s = [0]
for i in range(1, n_max + 1):
    s.append(s[i - 1] + is_2017[i])

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

Solution (Python):
def get_prime_list(n):
    l = [0 for _ in range(n)]
    i = 1
    while (i < n):
        for j in range(2, int((i + 1)**0.5) + 1):
            if not (i + 1) % j:
                break
        else:
            l[i] = 1
        i += 1

    return l


n_max = 10**5
is_prime = get_prime_list(n_max)
is_2017 = [0 for _ in range(n_max)]
for i in range(2, n_max + 1):
    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:
        is_2017[i - 1] = 1

s = [0]
for i in range(n_max):
    s.append(s[i] + is_2017[i])

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

Solution (Python):
import numpy as np
N = int(input())
queue = [list(map(int, input().split())) for _ in range(N)]


max_N = 100100
prime = np.ones(max_N, dtype=int)
a = np.zeros(max_N, dtype=int)
b = np.zeros(max_N+1, dtype=int)

prime[0], prime[1] = 0, 0
for i in range(2, max_N):
    if i == 0:
        continue
    for j in range(i*2, max_N, i):
        prime[j] = 0

for i in range(1, max_N):
    if i % 2 == 0:
        continue
    if prime[i] == 1 and prime[int((i + 1) / 2)] == 1:
        a[i] = 1
for i in range(0, max_N):
    b[i + 1] = a[i] + b[i]

for i in queue:
    print(b[i[1]+1]-b[i[0]])

Solution (Python):
import numpy as np
N = int(input())
queue = [list(map(int, input().split())) for _ in range(N)]


max_N = 100100
prime = list(np.ones(max_N, dtype=int))
a = list(np.zeros(max_N, dtype=int))
b = list(np.zeros(max_N+1, dtype=int))

prime[0], prime[1] = 0, 0
for i in range(2, max_N):
    if i == 0:
        continue
    for j in range(i*2, max_N, i):
        prime[j] = 0

for i in range(1, max_N):
    if i % 2 == 0:
        continue
    if prime[i] == 1 and prime[int((i + 1) / 2)] == 1:
        a[i] = 1
for i in range(0, max_N):
    b[i + 1] = a[i] + b[i]

for i in queue:
    print(b[i[1]+1]-b[i[0]])