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):
Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]
from math import sqrt
M = 10**5
Likes = [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]
C = [0 for _ in range(M)]
s = 0 
for i in range(M):
    if i in Likes:
        s += 1
    C[i] = s
for l,r in LR:
    print(C[r]-C[l-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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



n = 10 ** 5
prime_list = primes(n)
q = I()
C = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 and prime_list[i] and prime_list[(i + 1) // 2]:
        C[i] = 1


for j in range(1, n + 1):
    C[j] += C[j - 1]

for i in range(q):
    l, r = LI()
    print(C[r] - C[l - 1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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



n = 10 ** 5
prime_set = primes(n)
q = I()
C = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 and i in prime_set and (i + 1) // 2 in prime_set:
        C[i] = 1


for j in range(1, n + 1):
    C[j] += C[j - 1]

for i in range(q):
    l, r = LI()
    print(C[r] - C[l - 1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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



n = 10 ** 5
prime_set = primes(n)
q = I()
C = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 and i in prime_set and (i + 1) // 2 in prime_set:
        C[i] = 1


acc = list(accumulate(C))
for i in range(q):
    l, r = LI()
    print(acc[r] - acc[l - 1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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



n = 10 ** 5
prime_set = primes(n)
q = I()
C = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 and i in prime_set and (i + 1) // 2 in prime_set:
        C[i] = 1


acc = list(accumulate(C))
for i in range(q):
    l, r = LI()
    print(acc[r] - acc[l - 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

s=[0]*100007
s[2]=1
t=[0]*100007
for i in range(1,100001,2):
    s[i]+=is_prime(i)
for i in range(1,100001,2):
    t[i]=(s[i]+s[(i+1)//2])//2
for i in range(1,100007):
    t[i]+=t[i-1]
for i in range(int(input())):
    l,r=map(int,input().split())
    print(t[r]-t[l-1])

Solution (Python):


N = int(input().split()[0])
lr_table = []

for _ in range(N):
    l, r = list(map(int, input().split()))
    lr_table.append((l, r))





def get_prime_number_flag_list(n):
    
    
    pn_flag_list = [True] * (n + 1)
    pn_flag_list[0] = False
    pn_flag_list[1] = False
    for i in range(2, n + 1):
        if pn_flag_list[i]:
            for j in range(i + i, n + 1, i):
                
                pn_flag_list[j] = False
    return pn_flag_list


pn_flag_list = get_prime_number_flag_list(10 ** 5)

cumsum_list = []
for i in range(10 ** 5 + 1):
    if i in [0, 1]:
        cumsum_list.append(0)
        continue
    if pn_flag_list[i] and pn_flag_list[(i + 1) // 2]:
        cumsum_list.append(cumsum_list[i - 1] + 1)
    else:
        cumsum_list.append(cumsum_list[i - 1])

count_list = []
for lr_set in lr_table:
    l, r = lr_set
    
    count_list.append(cumsum_list[r] - cumsum_list[l - 1])

ans = "\n".join([str(c) for c in count_list])
print(ans)

Solution (Python):
import math
def like_2017(n):
    if n == 1: return False
    if n == 2: return False 

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
        
    for l in range(2,int(math.sqrt((n+1)/2)) + 1):
        if ((n+1)/2)%l ==0:
            return False
        
    return True

q = int(input())
L = [[int(i) for i in input().split()] for _ in range(q)]
ans = [0 for _ in range(10**5+1)]

for i in range(3,10**5):
    ans[i+1] = ans[i] + 1 if like_2017(i) else ans[i] 

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

Solution (Python):


N=int(input())

lr=[]
ma=0
for _ in range(N):
    l,r=map(int,input().split())
    ma=max(l,r,ma)
    lr.append([l,r])



l=[0]*(ma+1)

for n in range(3,ma+1)[::2]:
    temp=(n*(n+1))//2
    flag=True
    for i in range(2,-int(-temp**0.5//1)):
        if temp%i==0:
            if i!=(n+1)//2:
                
                flag=False
                break
    if flag:
        l[n]=l[n-2]+1
    else:
        l[n]=l[n-2]


for item in lr:
    print(l[item[1]]-l[item[0]] if l[item[0]-2]==l[item[0]] or item[0]==1 else l[item[1]]-l[item[0]]+1)

Solution (Python):
from bisect import bisect
q=int(input())
lr=[list(map(int,input().split())) for i in range(q)]
lst=[]
for i in  range(2,10**5):
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            break
    else:
          lst.append(i)
li=[]
data=[0]*(10**5)
for i in range(1,len(lst)):
    u=lst[i]
    v=(u+1)//2
    a=bisect(lst,v)
    if v==lst[a-1]:
        data[u]=1
for i in range(1,10**5):
    data[i]=data[i]+data[i-1]
for i in range(q):
    l,r=lr[i]
    print(data[r]-data[l-1])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



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



n = 10 ** 5
prime_set = primes(n)
q = I()
C = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 and i in prime_set and (i + 1) // 2 in prime_set:
        C[i] = 1


acc = list(accumulate(C))
for i in range(q):
    l, r = LI()
    print(acc[r] - acc[l - 1])

Solution (Python):
l=[0,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,100001]
L=[]
t=0
for i in range(673):
    L+=[i]*(l[i+1]-l[i])
Q=int(input())
for _ in range(Q):
    h,m=map(int,input().split())
    print(L[m]-L[h-1])

Solution (Python):

import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e%p != 0]

_primes = eratosthenes(10**5)
primes = [False] * (10**5+1)

for p in _primes:
    primes[p] = True

like_2017 = [False] * (10**5+1)
for p in _primes:
    if primes[(p+1)//2]:
        like_2017[p] = True

c = 0
C = [0]
for i in range(1,10**5+1):
    if like_2017[i]:
        c += 1
    C.append(c)

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

Solution (Python):
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return list[mid]
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return None



mx_int = 10**5
import math
li = [True for i in range(mx_int+1)]

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

li2 = []
for i in range(2,mx_int+1):
    if li[i]:
        li2.append(i)

li3 = []
for i in range(len(li2)):
    if (binary_search(li2,(li2[i]+1)//2)):
        li3.append(li2[i])
li3.append(0)

ans = []
flg = 0
for i in range(mx_int+1):
    if i == li3[flg]:
        flg += 1
    ans.append(flg)

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

Solution (Python):
q=int(input())
p=10**5+9 
isp=[1]*p 
i=2 
while i*i<=p: 
    if isp[i]:
        for j in range(i*i,p,i):
            isp[j]=0 
    i+=1 
isp[1]=isp[0]=0 
pre=[0]*p 

for i in range(2,p):
    if isp[i] and isp[(i+1)//2]:
        pre[i]=pre[i-1]+1 
    else:
        pre[i]=pre[i-1]


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

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from time import time

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

def main():
    q = int(input().strip())
    n = 10**5
    ary = [0] * (n+1)
    ary2 = [0] * (n+1)
    arys = [0] * (n+2)
    for i in range(2, n+1):
        ary[i] = is_prime(i)
    for i in range(1, n+1):
        ary2[i] = ary[i] & ary[(i+1)//2]
    for i in range(1, n+2):
        arys[i] = arys[i-1] + ary2[i-1]
    
    
    
    for i in range(q):
        l, r = map(int, input().strip().split())
        print(arys[r+1] - arys[l])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from time import time

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

def main():
    q = int(input().strip())
    n = 10**5
    ary = [0] * (n+1)
    ary2 = [0] * (n+1)
    arys = [0] * (n+2)
    for i in range(2, n+1):
        ary[i] = is_prime(i)
    for i in range(1, n+1):
        ary2[i] = ary[i] & is_prime((i+1)//2)
    for i in range(1, n+2):
        arys[i] = arys[i-1] + ary2[i-1]
    
    
    
    for i in range(q):
        l, r = map(int, input().strip().split())
        print(arys[r+1] - arys[l])

if __name__ == '__main__':
    main()

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

num = 10**5
primes = [1 for _ in range(num + 1)]
cum = [0 for _ in range(num+1)] 
primes[0] = 0
primes[1] = 0
cum_i = 0
for i in range(2,num+1):
    if primes[i]:
        k=1
        while i*(k+1)<num+1:
            k +=1
            primes[i*k] = 0
        
        if i>2:
            if primes[(i+1)//2]:
                cum_i +=1
    cum[i] = cum_i
q = int(readline())
for _ in range(q):
    l,r = map(int,readline().split())
    print(cum[r] - cum[l-1])

Solution (Python):
from sys import stdin
q = int(stdin.readline().rstrip())
prime_accum = [0] * 1000001

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    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]
    return data

prime = set(get_sieve_of_eratosthenes(100000))
    
cnt = 0
for i in range(1,100001):
    if i % 2 ==1 and (i in prime) and (((i+1)//2) in prime):
        cnt += 1
    prime_accum[i] = cnt

for _ in range(q):
    l,r = [int(x) for x in stdin.readline().rstrip().split()]
    print(prime_accum[r]-prime_accum[l-1])

Solution (Python):
import math
import bisect

num = (10**5) + 2

era = [i for i in range(3,num,2)]
i = 0
while era[i] <= math.sqrt(num):
    tmp = era[i]
    era = [j for j in era if j % era[i] != 0]
    era.insert(i,tmp)
    i += 1


era = [j for j in era if bisect.bisect_left(era,(j+1) // 2) != bisect.bisect_right(era,(j+1)//2)]
era.insert(0,3)

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

Solution (Python):

from math import sqrt
def sieve(n):
    if n<2:
        return [False]*(n+1)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return is_prime

n = int(1e5)
is_prime = sieve(n)

cnt = [0]*(n+1)
for i in range(1, n+1):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(cnt[r] - cnt[l-1])

Solution (Python):
import numpy as np
MAX = 10**5
isPrime = np.full(MAX+1,True)
isPrime[:2] = False
for p in range(2,MAX+1):
    if p*p > MAX: break
    if isPrime[p]: isPrime[p*p::p] = False

mat = np.zeros(MAX+1,np.int32)
for p in range(1,MAX+1):
    if 2*p > MAX: break
    if isPrime[p] and isPrime[2*p-1]: mat[2*p-1] = 1

cum = mat.cumsum()

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

Solution (Python):
def PrimeNumber(N):
    f=[1]*(N+1)
    f[0]=0
    f[1]=0

    for i in range(2,N+1):
        if f[i]==0:
            continue
        j = 2
        temp = i
        while temp * j <= N:
            f[temp*j]=0
            j += 1

    return f

PN=PrimeNumber(100000)
C=[0]*100001

C[1]=0

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

Q=int(input())

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

Solution (Python):


import sys
from itertools import accumulate

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

def eratosthenes_sieve(n):
    """ 素数列挙(エラトステネスの篩) """

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

N = 100000
primes = set(eratosthenes_sieve(N+1))

A = [0] * (N+1)
for a in range(1, N+1, 2):
    if a in primes and (a+1)//2 in primes:
        A[a] = 1

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

Solution (Python):
MAX = 100010


is_p =[1]*MAX
is_p[0] = 0
is_p[1] = 0

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


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


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


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

Solution (Python):
import bisect

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

N=[3]
for i in range(5,100001,2):
    if PN(i) and PN((i+1)//2):
        N.append(i)

Q=int(input())

for i in range(Q):
    l,r=map(int,input().split())
    ln1=bisect.bisect_left(N,l)
    ln2=bisect.bisect_right(N,l)
    rn1=bisect.bisect_left(N,r)
    rn2=bisect.bisect_right(N,r)
    if ln1==ln2 and rn1==rn2:
        print(rn1-ln1)
    elif ln1==ln2 or rn1==rn2:
        print(rn1-ln2+1)
    else:
        print(rn1-ln2+2)

Solution (Python):
def prime(n):
  if n==1:
    return False
  elif n==2:
    return True
  else:
    for i in range(2,int((n)**(1/2))+1):
      if n%i==0:
        return False
    return True
list=[True]*100001
for i in range(1,100001):
  if not prime(i):
    list[i]=False
list1=[0]
count=0
for i in range(1,100001):
  if i%2==1:
    if list[i] and list[(i+1)//2]:
      count+=1
  list1.append(count)
n=int(input())
for i in range(n):
  a,b=map(int,input().split())
  print(list1[b]-list1[a-1])