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
def input():return sys.stdin.readline().strip()
from itertools import accumulate

def islike2017_list(n):
    primes = [True] * (n+1)
    primes[0] = False
    primes[1] = False

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


def main():
    Q = int(input())
    queries = [tuple(map(int, input().split())) for _ in range(Q)]

    MAX_X = 10**5
    like2017 = islike2017_list(MAX_X)
    CUSUM = tuple(accumulate(like2017))

    ans = [CUSUM[r] - CUSUM[l-1] for l, r in queries]
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from bisect import bisect_left, bisect_right


def seachPrimeNum(N):
    max = int(np.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


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


sosu = seachPrimeNum(10**5)[1:]
like_2017 = [i for i in sosu if is_prime((i+1) / 2)]

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    l_ix = bisect_left(like_2017, l)
    r_ix = bisect_right(like_2017, r)
    print(r_ix - l_ix)

Solution (Python):

from itertools import accumulate


def get_prime(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return []
    if n == 2:
        return [2]
    prime = [2]
    limit = int(n ** 0.5)
    nums = [i + 1 for i in range(2, n, 2)]
    while True:
        p = nums[0]
        if limit < p:
            return prime + nums
        prime.append(p)
        nums = [e for e in nums if e % p != 0]


primes = set(get_prime(10 ** 5))
like = [0] * 10 ** 5
for i in range(3, 10**5):
    if i in primes and (i + 1) // 2 in primes:
        like[i] = 1

like_accum = list(accumulate(like))

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

Solution (Python):
from bisect import bisect_left, bisect_right
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(3,n + 1) if is_prime[i]]

prime = primes(10**5)
p_set = set(prime)
like = [3]
for i in prime:
    if (i+1)//2 in p_set:
        like.append(i)

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

Solution (Python):
from bisect import bisect_left, bisect_right
import random
def is_prime(q,k=50):
    q = abs(q)
    
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
 
    
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

prime = []
like = [3]
for i in range(3, 10**5+1):
    if is_prime(i):
        prime.append(i)
p_set = set(prime)
for i in prime:
    if (i+1)//2 in p_set:
        like.append(i)

Q = int(input())

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

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

minl = 10**9
maxr = -1
ans_range = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans_range.append((l, r))

    if l < minl:
        minl = l
    if r > maxr:
        maxr = r

dp = [0] * ((maxr - minl) + 2)

import math
for u in range(minl, maxr+1,1):
    check = (u + 1) / 2

    if not float.is_integer(check) or check == 1:
        dp[u - minl + 1] = dp[u-minl]
        continue

    ok = True
    for y in range(2, int(math.sqrt(check))+1):
        if check % y == 0:
            ok = False
            break

    ok2 = True
    for z in range(2, int(math.sqrt(u))+1):
        if u % z == 0:
            ok2 = False
            break
    
    if ok and ok2:
        
        dp[u - minl + 1] = dp[u-minl] + 1
    else:
        
        dp[u - minl + 1] = dp[u-minl]


for ll, rr in ans_range:
    if ll == rr:
        ans = dp[rr-minl+1] - dp[rr-minl]
    else:
        ans = dp[rr-minl+1] - dp[ll-minl]
    print(ans)

Solution (Python):
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[c:] = add 
b[0::2] = 0

for i in range(n):
    l, r =map(int,input().split())
    print(b[r] - b[max(0, l - 2)] )

Solution (Python):
import math
import numpy as np
def get_prime(n):
    if n<= 1:
        return[]
    prime = [2]
    limit = int(math.sqrt(n))
    
    data = [i + 1 for i in range(2,n,2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j % data[0] != 0]
    return prime + data
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
n = int(input())
l = []
r = []
for i in range(n):
    l_, r_ =map(int,input().split())
    l.append(l_)
    r.append(r_)
a = get_prime(10**5+1)
b = np.array([0]*(10**5+2))
c =0
d = 0
add = 0
for i in range(1,len(a)):
    if is_prime((a[i]+1)/2):
        d = a[i] 
        b[c:d] = add 
        c = d
        add +=1
b[c:] = add 
b[0::2] = 0
for i in range(n):
    e = b[max(0, l[i] - 2)]
    f = b[r[i]]
    print(f - e)

Solution (Python):
q = int(input())
l, r = [0] * q, [0] * q
for i in range(q):
    l[i], r[i] = map(int, input().split())
 
mini = min(min(l), min(r))
maxi = max(max(l), max(r))
ans = [0] * (maxi + 1)
prime = [0] * (maxi + 1)
def judge_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    
    return True if n != 1 else False
 
for i in range((mini + 1) // 2, maxi + 1):
    prime[i] = judge_prime(i)
 
for i in range(mini, maxi + 1, 2):
    ans[i] = ans[i - 2] + 1 if prime[i] and prime[(i + 1) // 2] else ans[i - 2]
for i in range(q):
    print(ans[r[i]] - ans[max(0, l[i] - 2)])

Solution (Python):
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
mr=0
for l,r in lr:
  mr=max(mr,r)
l=[1 for _ in range(mr+1)]
l[0],l[1]=0,0
s=[0 for _ in range(mr+1)]
for i in range(2,int(mr**(1/2))+1):
  x=i*2
  while x<=mr:
    l[x]=0
    x+=i
for i in range(2,mr+1):
  if l[i]==1 and l[(i+1)//2]==1:
    s[i]=s[i-1]+1
  else:
    s[i]=s[i-1]
for l,r in lr:
  print(s[r]-s[l-1])

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

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

prime = sieve_of_eratosthenes(10**5 + 1)

numlike2017 = [0 for i in range(10**5 + 1)]
for i in prime:
    if (i+1)//2 in prime:
        numlike2017[i] = 1

def cumulative_sum(collection):
    result = [collection.pop(0)]
    for item in collection:
        result.append(result[-1] + item)
    return result
cs2017 = cumulative_sum(numlike2017)

ans = []
for i in range(n):
    a, b = map(int, input().split())
    ans.append(cs2017[b] - cs2017[a-1])

for i in ans:
    print(i , flush=True)

Solution (Python):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    """
    エラトステネスの篩。√N以下の数に対して2から順にその数の倍数を消していく。
    計算量は「調和級数」になるのがミソ。具体的には
        N/2 + N/3 + N/5 + ... + N/(√N) = N * (1/2 + 1/3 + 1/5 + ... + 1/√N)
                                       = N * loglog(√N) (素数の逆数和の発散スピードがこれ)
                                       = N(loglogN - log2)
    """
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return []
    prime = [1] * (n + 1)
    prime[0] = prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not prime[i]: continue
        for j in range(i * 2, n + 1, i):
            prime[j] = 0
    return prime


def main():
    primes = get_sieve_of_eratosthenes(100000)
    like = [0] * 10**5
    for i in range(3, 10**5):
        if primes[i] and primes[(i + 1) // 2]:
            like[i] = 1
    like = list(accumulate(like))

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        if l < 3: l = 3
        if r < 3:
            print(0)
            continue
        print(like[r] - like[l - 1])



if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_cumulative(A):
    C = [0] * (len(A) + 1)
    for i, a in enumerate(A):
        i += 1
        C[i] = C[i - 1] + a
    return C


def main():
    Q = NI()
    querys = [NLI() for _ in range(Q)]
    N = 100010
    hurui = [1] * N
    for i in range(N):
        if i <= 1:
            hurui[i] = 0
            continue
        if hurui[i] == 0:
            continue
        for j in range(i*2, N, i):
            hurui[j] = 0
    like_2017 = hurui[:]
    for i in range(N):
        if hurui[i] == 0 or i <= 2:
            continue
        if hurui[(i+1)//2] == 0:
            like_2017[i] = 0
    like_2017[2] = 0
    C = make_cumulative(like_2017)[1:]

    for q in querys:
        print(C[q[1]] - C[q[0]-1])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def get_sieve_of_eratosthenes(n):
    """
    エラトステネスの篩。√N以下の数に対して2から順にその数の倍数を消していく。
    計算量は「調和級数」になるのがミソ。具体的には
        N/2 + N/3 + N/5 + ... + N/(√N) = N * (1/2 + 1/3 + 1/5 + ... + 1/√N)
                                       = N * loglog(√N) (素数の逆数和の発散スピードがこれ)
                                       = N(loglogN - log2)
    """
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return []
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit < p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def main():
    primes = get_sieve_of_eratosthenes(100000)
    like = [0] * 10**5
    for i in range(3, 10**5):
        if i in primes and (i + 1) // 2 in primes:
            like[i] = 1
    like = list(accumulate(like))

    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        if l < 3: l = 3
        if r < 3:
            print(0)
            continue
        print(like[r] - like[l - 1])



if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    MAX_NUM = 10 ** 5
    Q = int(input())
    lr = [None] * Q
    for i in range(Q):
        lr[i] = tuple(map(int, input().split()))

    is_prime = [True] * (MAX_NUM + 1)
    is_prime[0] = False
    for i in range(4, MAX_NUM + 1, 2):
        is_prime[i] = False

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

    S = {}
    S[-1] = 0
    for i in range(1, MAX_NUM + 1, 2):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            S[i] = S[i - 2] + 1
        else:
            S[i] = S[i - 2]

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


if __name__ == "__main__":
    main()

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

primes=[True]*100001
primes[0]=False
primes[1]=False

for i in range(2,100001):
    if primes[i]:
        for j in range(2,100000//i+1):primes[i*j]=False

sim2017=[0]*100001
for i in range(3,100001,2):
    sim2017[i]=sim2017[i-2]+(1 if primes[i] and primes[(i+1)//2] else 0)

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

Solution (Python):
from math import sqrt
def sieve(n):
    if n <= 4:
        return list(range(2, n))
    def _sieve_of_eratosthenes(n):
        limit = int(sqrt(n))+1
        table = [1] * n
        table[0] = table[1] = 0
        for i in range(2, limit):
            if table[i]:
                for j in range(i**2, n, i):
                    table[j] = 0
        return [i for i in range(2, n) if table[i]]
    return _sieve_of_eratosthenes(n)

q, *LR = map(int, open(0).read().split())
P = set(sieve(10**5))
d = {-1:0}
s = 0
for i in range(1, 10**5, 2):
    s += i in P and (i+1)//2 in P
    d[i] = s
for l, r in zip(LR[::2], LR[1::2]):
    print(d[r] - d[l-2])

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

mini = min(min(l), min(r))
maxi = max(max(l), max(r))
ans = [0] * (maxi + 1)
prime = [0] * (maxi + 1)
def judge_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    
    return True if n != 1 else False

for i in range((mini + 1) // 2, maxi + 1):
    prime[i] = judge_prime(i)

for i in range(mini, maxi + 1, 2):
    ans[i] = ans[i - 2] + 1 if prime[i] and prime[(i + 1) // 2] else ans[i - 2]
for i in range(q):
    print(ans[r[i]] - ans[max(0, l[i] - 2)])

Solution (Python):
def get_primes(n):
    is_prime = [True]*(n+1)
    is_prime[0] = 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]]

from itertools import accumulate
import sys
input = sys.stdin.readline

MAX = 100_000
primes = set(get_primes(MAX))
like = [0]*MAX
for n in range(MAX):
    if n in primes and (n+1)//2 in primes:
        like[n] = 1
like = list(accumulate(like))

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

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

q = ii()
rmax = 0
qer = []
for i in range(q):
    l,r = mi()
    qer.append([l,r])
    if rmax < r:
        rmax = r






import math
primeList = [2,3,5,7,11,13]
for i in range(17,rmax+1,2):
    for j in primeList:
        if j > math.sqrt(i):
            primeList.append(i)
            break
        if i % j == 0:
            break


        
def checksim(x,pl):
    if x in pl and (x+1)//2 in pl:
        return 1
    return 0

tans = [0] * (rmax+1)
tans[3] = 1
for i in range(5,rmax+1,4):
    if checksim(i, primeList):
        tans[i] = 1


ans = [0]*(rmax+1)
tcumsum = 0
for i in range(rmax+1):
    if tans[i] == 1:
        tcumsum += 1
    ans[i] = tcumsum

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

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

a = [1]*(10**5+1)
a[0] = a[1] = a[2] = 0

for i in range(2, ceil(sqrt(10**5)+1)):
    for j in range(i*2, len(a), i):
        a[j] = 0
        if j*2 - 1 < len(a):
            a[j*2-1] = 0

q = INT()
p = [LIST() for i in range(q)]
s = list(accumulate(a))

for i in range(q):
    print(s[p[i][1]]-s[p[i][0]-1])

Solution (Python):
B = [False]*100005
C = [0]*100005
for i in range(2,100001):
    if not B[i]:
      	for j in range(i+i,100001,i):
          	B[j]=True
for i in range(3,100001,2):
    if not B[i] and not B[(i+1)//2]:
        C[i]+=1
for i in range(3,100001):
    C[i]=C[i]+C[i-1]
    
N = int(input())
for _ in range(N):
    a, b = map(int,input().split())
    print(C[b]-C[a-1])

Solution (Python):
q=int(input())
n=10**5

work=[1 if i%2==1 else 0 for i in range(n+1)]
primes=[2]
lst=[0]*(n+1)
work[1]==0

for i in range(3,n,2):
    if not work[i]: continue
    primes.append(i)
    index=1
    while i*index<=n:
        work[i*index]=0
        index+=1

for i in primes[1:]:
    if (i+1)//2 in primes:
        lst[i]=1

for i in range(3,n+1):
    lst[i]+=lst[i-1]

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



q = int(input())
lr = [None]*q
for i in range(q):
    lr[i] = tuple(map(int, input().split()))
n = max(item[1] for item in lr) + 10

def hurui(n):
    """n以下の素数のリストを返す
    """
    l = list(range(2,n+1))
    p = 2
    i = 0
    while True:
        l = [item for item in l if item==p or item%p!=0]
        i += 1
        p = l[i]
        if p*p>n:
            break
    return l
l = hurui(n)
l = set(l)
v = [0]*n 
c = 0
for i in range(n):
    if i%2==1 and i in l and (i+1)//2 in l:
        c += 1
    v[i] = c
ans = []
for l,r in lr:
    ans.append(v[r]-v[l-1])
write("\n".join(map(str, ans)))

Solution (Python):
def generate_is_prime_sieve(N):
	is_prime = [True]*(N+1)
	is_prime[0] = is_prime[1] = False
	for p in range(2,N+1):
		if is_prime[p]:
			for n in range(2*p,N+1,p):
				is_prime[n] = False
	dummy=[x for x in is_prime]
	for p in range(2,N+1):
		if is_prime[p] and is_prime[(p+1)//2]:
			dummy[p]=True
		else:
			dummy[p]=False
	return dummy
def partial_sums(N):
	something=generate_is_prime_sieve(N)
	counter=0
	partial_sum=[0]*(N+1)
	for i in range(N+1):
		if something[i]:
			counter+=1
		partial_sum[i]=counter
	return partial_sum	
N=partial_sums(10**5+1)
for i in range(int(input())):
	counter=0
	a,b=[int(x) for x in input().split()]
	print(N[b]-N[a-1])

Solution (Python):
import math

q = int(input())

def is_prime(a):
    if a == 1:
        return False
    for i in range(2,int(math.sqrt(a)+1)):
        if a%i == 0:
            return False
    else:
        return True

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

s2 = [0 for i in range(0,100001)]
tmp = 0
for i in range(100001):
    tmp += s[i]
    s2[i] = tmp

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

Solution (Python):
import sys
import numpy as np

input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    
    N = pow(10, 5)
    is_prime = np.ones(N, dtype=bool)
    is_prime[:2] = False
    max = int(np.sqrt(N))
    for j in range(2, max + 1):
        if (is_prime[j]):
            is_prime[j*j::j] = False
    like_2017 = np.ones(N, dtype=bool)
    like_2017[:2] = False
    for i in range(2, N):
        if (i % 2 == 0):
            like_2017[i] = False
            continue
        if (not is_prime[i]):
            like_2017[i] = False
            continue
        if (not is_prime[(i + 1) // 2]):
            like_2017[i] = False
            continue

    cumsum = np.cumsum(like_2017)
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().rstrip().split())
        print(cumsum[r] - cumsum[l - 1])


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
INF = float('inf')


def prime_numbers(n):
    if n < 2:
        return []

    m = (n + 1) // 2
    p = [True] * m
    for i in range(1, int((n ** 0.5 - 1) / 2) + 1):
        if p[i]:
            for j in range(2 * i * (i + 1), m, 2 * i + 1):
                p[j] = False
    
    a = [2 * i + 1 for i in range(m) if p[i]]
    a[0] = 2
    return a


N = 10 ** 5
P = set(prime_numbers(N))


P = [n for n in P if (n + 1) // 2 in P]


a = [0] * (N + 1)
for n in P:
    
    a[n] = 1

a = list(accumulate(a))


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

Solution (Python):
like2017numbers = {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}
N = 10**5
dp_table = [0]*(N+1)
for i in range(N):
    if i+1 in like2017numbers:
        dp_table[i+1] = dp_table[i]+1
    else:
        dp_table[i+1] = dp_table[i]

def solve():
    Q = int(input())
    for _ in range(Q):
        l,r = map(int, input().split())
        
        print(dp_table[r]-dp_table[l-1], flush=True)
        
solve()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



lim = 10**5

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

for i in range(lim+1):
	if is_prime[i] == 1:
		for j in range(2, lim//i + 1):
			is_prime[i*j] = 0

dp = [0]*(lim+1)
for i in range(lim+1):
	if is_prime[i] and is_prime[(i+1)//2]:
		dp[i] = 1

dp = list(accumulate(dp))

Q = INT()
for _ in range(Q):
	l, r = MAP()
	print(dp[r]-dp[l-1])

Solution (Python):
INF=10**5+1
p=[1]*INF
for i in range(2,INF):
  if p[i]:
    for j in range(2*i,INF,i):p[j]=0
p[0],p[1]=0,0
q=[0]*INF
for i in range(INF):
  if i%2==0:continue
  if p[i]*p[(i+1)//2]:q[i]=1
for i in range(1,INF):
  q[i]+=q[i-1]
n=int(input())
for _ in range(n):
  l,r=map(int,input().split())
  print(q[r]-q[l-1])

Solution (Python):
prime = [1]*(100001)
prime[0] = 0
prime[1] = 0
for i in range(2,100001):
    if prime[i]:
        for j in range(i*i,100001,i):
            prime[j] = 0

for i in range(100000,-1,-1):
    if prime[i]:
        if prime[(i+1)//2] != 1:
            prime[i] = 0

from itertools import accumulate
accum = list(accumulate(prime))

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

Solution (Python):
import math
def eraP(n):
    if n<=1: return [False]*(n+1)
    elif n<=2: return [False, False, True]
    L = [False if i%2==0 or i%3==0 else True for i in range(n)]
    L[0] = False; L[1] = False;
    L[2] = True; L[3] = True; L[5]=True
    limit = math.sqrt(n)
    for i in range(3,n,2):
        if i >= limit: return L
        for s in range(i**2,n,i):
            L[s] = False
    return L

q = int(input())
LR = [[0,0] for _ in range(q)]
for i in range(q):
    LR[i] = list(map(int, input().split()))
P = eraP(pow(10,5)+1)[1:]

sumP = [0,0,0]
for i in range(2,pow(10,5)):
    sumP.append(sumP[-1]+int(P[i] and P[(i+1)//2]))

for lr in LR:
    print(sumP[lr[1]]-sumP[lr[0]-1])

Solution (Python):
import math


def IsPrime(n):
    if n == 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

q = int(input())

a = [0] * (10**5 + 1)

for i in range(10**5 + 1):
    
    if IsPrime(i) and IsPrime((i + 1) / 2) and i % 2 == 1:
        a[i] = 1
    else:
        a[i] = 0


for i in range(10**5):
    a[i + 1] += a[i]


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

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

MAX=10**5+1
l=[0]*MAX

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
cnt=0
for i in range(1, MAX, 2):
  if is_prime(i) and is_prime((i+1)/2):
    l[i]=1
    
l2=[0]*(MAX+1)
for i in range(0, MAX):
  l2[i+1]=l2[i]+l[i]


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

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

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

acm = [0] * (10 ** 5 + 1)
for i in range(10**5):
    acm[i+1] = acm[i] + p[i]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(acm[r+1] - acm[l])