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


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

Solution (Python):
from itertools import accumulate


def get_primes_til(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** .5) + 1):
        if is_prime[i]:
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return {i for i in range(2, n + 1) if is_prime[i]}


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([i in primes and (i + 1) // 2 in primes for i in range(N_MAX + 1)]))
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Solution (Python):
from itertools import accumulate


def get_primes_til(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, int(n ** .5) + 1):
        for j in range(2 * i, n + 1, i):
            primes[j] = False
    return {i for i in range(2, n + 1) if primes[i]}


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([i in primes and (i + 1) // 2 in primes for i in range(N_MAX + 1)]))
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Solution (Python):
from itertools import accumulate


def get_primes_til(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, int(n ** .5) + 1):
        for j in range(2 * i, n + 1, i):
            primes[j] = False
    return primes


N_MAX = 10 ** 5
is_prime = get_primes_til(N_MAX)
is_2017_like = list(accumulate([1 if is_prime[i] and is_prime[(i + 1) // 2] else 0 for i in range(N_MAX + 1)]))
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Solution (Python):
from itertools import accumulate


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

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N_MAX = 10 ** 5
primes = get_prime_numbers_til(N_MAX)
is_2017_like = list(accumulate([1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(N_MAX + 1)]))
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Solution (Python):
from itertools import accumulate


def get_primes_til(n):
    primes = [True] * (n + 1)
    primes[0] = False
    primes[1] = False
    for i in range(2, int(n ** .5) + 1):
        for j in range(2 * i, n + 1, i):
            primes[j] = False
    return primes


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([int(primes[i] and primes[(i + 1) // 2]) for i in range(N_MAX + 1)]))
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(is_2017_like[r] - is_2017_like[l - 1])

Solution (Python):
import math
primes = [True]*(10**5+1)
primes[0],primes[1] = False,False
cumsum = [0]*(10**5+1)

for i in range(2, int(math.sqrt(10**5)+1)):
  if primes[i]:
    j = 2
    while i*j <= 10**5:
      primes[i*j] = False
      j += 1

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

Q = int(input())
for _ in range(Q):
  l,r = map(int,input().split())
  print(cumsum[r]-cumsum[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 [i for i in range(n + 1) if is_prime[i] and is_prime[(i+1)//2]]


d = primes(100000)
cumsum = [0]
for i in range(1, 100001):
    if i in d:
        cumsum.append(cumsum[-1] + 1)
    else:
        cumsum.append(cumsum[-1])

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

Solution (Python):



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

from math import sqrt
def prime(n):
    if n<2:
        return False
    for i in range(2,int(sqrt(n)+1)):
        if n%i==0:
            return False
    return True
n=10*5-1
dp=[0 for i in range(10**5//2)]
dp[0]=0
for i in range(1,10**5//2):
    odd=2*i+1
    if prime(i+1) and prime(odd):
        dp[i]=dp[i-1]+1
    else:
        dp[i]=dp[i-1]
q=I()
for i in range(q):
    a,b=MI()
    if a==1:
        print(dp[(b+1)//2-1])
    else:
        print(dp[(b+1)//2-1]-dp[(a+1)//2-2])

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

def pri(N):
  x = (N + 1) // 2
  root = int(N ** (1/ 2))
  for i in range(2, root + 1):
    if N % i == 0:
      return 0
    if (x > i) and (x % i == 0):
      return 0
  return 1
  
prime = [0] * (10 ** 5)
for i in range(3, 10 ** 5):
  if i % 2 == 1:
    add = pri(i)
    prime[i] = prime[i - 2] + add
    
for i in range(Q):
  l, r = map(int, input().split())
  if l == 1:
    minus = 0
  else:
    minus = prime[l - 2]
  print(prime[r] - minus)

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

is_prime = [1 for i in range(10**5+1)]
is_prime[0] = is_prime[1] = 0
for i in range(10**5+1):
    if not is_prime[i]:
        continue
    for j in range(i*2, 10**5+1, i):
        is_prime[j] = 0
        
a = [0 for i in range(10**5+1)]
for i in range(10**5+1):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1
        
s = [0 for i in range(10**5+2)]
for i in range(10**5+1):
    s[i+1] = s[i] + a[i]
    
for i in range(Q):
    lr = lr_list[i]
    print(s[lr[1]+1] - s[lr[0]])

Solution (Python):
"""
10^5以下の素数を列挙しておく。
それをもとに、10^5以下の各整数以下の2017に似た数の個数のメモを作成する。
"""

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

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

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

Solution (Python):
import math

q = int(input())
cnt = [0] * (5 * 10 ** 4)
cnt[1] = 1
cnt[2] = 2


def is_prime(n):
    visit = []
    if n % 2 == 0:
        return 0
    for i in range(3, 1 + math.ceil(n ** (0.5))):
        if i not in visit:
            if n % i == 0:
                return 0
            else:
                visit.append(i)
    return 1


for i in range(3, 5 * 10 ** 4):
    odd = 2 * i + 1
    if odd % 3 != 1 or (odd + 1) % 4 == 0:
        cnt[i] = cnt[i - 1]
    else:
        k = 0
        if is_prime(odd) and is_prime((odd + 1) // 2):
            k = 1
            
        cnt[i] = cnt[i - 1] + k
cnt.append(0)
for i in range(q):
    l, r = map(int, input().split())
    print(cnt[(r - 1) // 2] - cnt[(l - 3) // 2])

Solution (Python):
import math










def erastosthenes(num):
    input_list = [False if i % 2 == 0 else True for i in range(num)]
    input_list[0] = False
    input_list[1] = False
    input_list[2] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            prime_list = [i for i, b in enumerate(input_list) if b]
            return prime_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False


def main():
    Q = int(input())
    l = [0] * (Q + 1)
    r = [0] * (Q + 1)
    for i in range(1, Q + 1):
        l[i], r[i] = map(int, input().split())

    prime_list = set(erastosthenes(10**5))
    count_list = [0] * (10**5 + 1)

    for i in range(1, 10**5 + 1):

        if not i % 2 == 0:
            i2 = (i + 1) / 2
            if i in prime_list and i2 in prime_list:
                count_list[i] = count_list[i - 1] + 1
            else:
                count_list[i] = count_list[i - 1]
        else:
            count_list[i] = count_list[i - 1]

    for q in range(1, Q + 1):
        ans = count_list[r[q]] - count_list[l[q] - 1]
        print(ans)


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

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 table
  
prime = sieve(10**5)
acu = [0] * ((10**5)//2+5)
for i in range(1,(10**5)//2+5):
    k = (i-1) * 2 +1
    if k in prime and (k+1)//2 in prime:
        acu[i] = acu[i-1] + 1
    else:
        acu[i] = acu[i-1]

q = int(input())

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

Solution (Python):
def prime(n):
    a = [1]*(n+1)
    a[0],a[1] = 0,0
    for i in range(2,int(n**(0.5))+1):
        j = 2
        while i*j <= 10**5:
            a[i*j] = 0
            j += 1
    return a

def like2017(a):
    c = [0]*(10**5+1)
    for i in range(3,10**5+1):
        if a[i]*a[(i+1)//2]:
            c[i] = 1
    return c

def ssum(c):
    s = [0]*(10**5+1)
    for i in range(2,10**5+1):
        s[i] = s[i-1]+c[i]
    return s

def s(lst,l,r):
    return lst[r]-lst[l-1]


q = int(input())
a = prime(10**5)
c = like2017(a)

ss = ssum(c)
for i in range(q):
    l,r = map(int,input().split())
    print(s(ss,l,r))

Solution (Python):
import itertools

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

p_list = primes(101010)
cnt_list = [0] * 101010

for i in range(1, 101011, 2):
    if p_list[i] and p_list[(i + 1) // 2]:
        cnt_list[i] = 1

cnt_list = list(itertools.accumulate(cnt_list))

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

Solution (Python):
import math


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 prime_table(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

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

table = prime_table(max(r))
s = [0] * (max(r)+1)
for i in range(1, max(r)+1):
    if table[i] == 1 and is_prime((i+1)//2):
        s[i] = s[i-1] + 1
    else:
        s[i] = s[i-1]


for i in range(q):
    ans = s[r[i]] - s[l[i]-1]
    print(ans)

Solution (Python):
def check_prime(k):
    '''
    素数の時1、合成数の時0を返す
    '''
    if k == 1:return 0
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:return 0
    return 1

q = int(input())
lr = []
l_min = 10 ** 9
r_max = 0
for i in range(q):
    l, r = map(int,input().split())
    lr.append((l, r))
    if l < l_min:l_min = l
    if r > r_max:r_max = r

pre_cal = [0] * (r_max - l_min + 2)
dic = {}
for num in range(l_min, r_max + 1):
    pre_cal[num - l_min + 1] = pre_cal[num - l_min]
    if num % 2 == 0:continue
    if not check_prime(num):continue
    dic[num] = 1
    temp = (num + 1) // 2

    if dic.get(temp, 0):
        pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1
    else:
        if check_prime(temp):
            dic[temp] = 1
            pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1

for l, r in lr:
    ans = pre_cal[r - l_min + 1] - pre_cal[l - l_min]
    print(ans)

Solution (Python):
def get_prime(x):
    l = [True] * (x + 1)
    l[0] = False
    l[1] = False
    for i in range(2,int(x**0.5) + 1):
        if not l[i]:
            continue
        for j in range(i * 2, x + 1, i):
            l[j] = False
    return l        
q=int(input())
table = get_prime(100000)
s=[0]*(100001)

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

for i in range(100000):        
    s[i+1] += s[i]

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

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

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

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


def main():
    N = 10 ** 5
    primes = prime_numbers(N)
    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
    a = tuple(accumulate(a))

    ans = []
    Q, *LR = map(int, open(0).read().split())
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(a[r] - a[l - 1])

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}

def main():
    N = 10 ** 5
    primes = prime_numbers(N)
    a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
    a = tuple(accumulate(a))

    ans = []
    Q, *LR = map(int, open(0).read().split())
    for l, r in zip(*[iter(LR)] * 2):
        ans.append(a[r] - a[l - 1])

    print('\n'.join(map(str, ans)))

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = tuple(accumulate(a))

ans = []
Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

print('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

ans = []
Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

print('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

ans = []
Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    ans.append(a[r] - a[l - 1])

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

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [1 if n in primes and (n + 1) // 2 in primes else 0 for n in range(N + 1)]
a = list(accumulate(a))

Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    print(a[r] - a[l - 1])

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    return {2} | {2 * i + 1 for i in range(1, m) if p[i]}


N = 10 ** 5
primes = prime_numbers(N)
a = [n in primes and (n + 1) // 2 in primes for n in range(N + 1)]
a = list(accumulate(a))

Q, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    print(a[r] - a[l - 1])

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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, *LR = map(int, open(0).read().split())
for l, r in zip(*[iter(LR)] * 2):
    print(a[r] - a[l - 1])

Solution (Python):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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):
from sys import stdin, setrecursionlimit
from itertools import accumulate

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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):
def isPrime(x):
    if x < 2:
        return 0
    elif x == 2:
        return 1
    if x%2 == 0:
        return 0
    ir=int(x**(0.5))+1
    for i  in range(3,ir,2) :
        if x%i == 0:
            return 0
    return 1

q=int(input())

l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
    
ps=[0]
pcnt=0
for i in range(1,max(r)+1):
    if i%2==1 and isPrime(i) and isPrime((i+1)//2):
        pcnt+=1
    ps.append(pcnt)        



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

Solution (Python):
from math import sqrt
from bisect import bisect_right

def eratos(n):
    L = [True for _ in range(n+1)]
    L[0],L[1] = False,False

    for i in range(2,int(sqrt(n))+1):
        if L[i]:
            for j in range(2,n//i+1):
                L[i*j] = False

    P = []
    for i in range(n+1):
        if L[i]:
            P.append(i)

    return P

def sim(P):
    
    
    P_set = set(P)
    P_sim = []
    for i in range(len(P)):
        if (P[i]+1)//2 in P_set:
            P_sim.append(P[i])

    return P_sim

def main():
    Q = int(input())

    P = eratos(10**5)
    P_sim = sim(P)

    ans_L = []
    for i in range(Q):
        l,r = map(int,input().split())
        ans = bisect_right(P_sim,r)-bisect_right(P_sim,l-1)
        ans_L.append(ans)

    for i in range(Q):
        print(ans_L[i])

if __name__ == "__main__":
    main()

Solution (Python):
from math import sqrt
from bisect import bisect_right

def eratos(n):
    L = [True for _ in range(n+1)]
    L[0],L[1] = False,False

    for i in range(2,int(sqrt(n))+1):
        if L[i]:
            for j in range(2,n//i+1):
                L[i*j] = False

    P = []
    for i in range(n+1):
        if L[i]:
            P.append(i)

    return P

def isPrime(n):
    if n == 1:
        return False

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

def sim(P):
    
    P_sim = []
    for i in range(len(P)):
        if isPrime((P[i]+1)//2):
            P_sim.append(P[i])

    return P_sim

def main():
    Q = int(input())

    P = eratos(10**5)
    P_sim = sim(P)

    ans_L = []
    for i in range(Q):
        l,r = map(int,input().split())
        ans = bisect_right(P_sim,r)-bisect_right(P_sim,l-1)
        ans_L.append(ans)

    for i in range(Q):
        print(ans_L[i])

if __name__ == "__main__":
    main()

Solution (Python):
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

Q = int(input())
primes = sieve_eratosthenes(10**5)
C = [0]*(10**5+1)
for x in range(1,10**5+1):
    if primes[x] == 1 and primes[(x+1)//2] == 1:
        C[x] = C[x-1] + 1
    else:
        C[x] = C[x-1]

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

Solution (Python):
def main():

    def hurui():
        N = 10 ** 5
        p = [1] * (N+1)
        p[0], p[1] = 0, 0
        for i in range(4, N+1, 2): p[i] = 0
        for i in range(3, N+1):
            if i * i > N: break
            if p[i]:
                for j in range(i, N+1):
                    if i*j > N: break
                    p[j*i] = 0
        return p

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

    Q = int(input())
    query = [[int(_) for _ in input().split()] for __ in range(Q)]
    for a, b in query:
        print(r[b+1] - r[a])
    return

if __name__ == '__main__':
    main()

Solution (Python):
"""
事前に、100000以下の数のうち、2017に似た数を列挙しておく。
メモの仕方としては、2017に似た数を小さい順に並べておけばよい。
2017に似た数を探すのは、まず100000以下の素数を全部列挙して、その中で条件に当てはまるものを愚直に探す。
"""
memo = [1]*(100001)
memo[0] = 0
memo[1] = 0
primes = set()
for i in range(100001):
    if memo[i] == 1:
        primes.add(i)
        for j in range(i*2,100001,i):
            memo[j] = 0

answers = []
for p in primes:
    if (p+1)//2 in primes:
        answers.append(p)

Q = int(input())
for _ in range(Q):
    ans = 0
    l,r = map(int,input().split())
    for a in answers:
        if l<=a<=r:
            ans += 1
    print(ans)