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



Sample input:
1
3 7


Sample output:
2

Submission status: Accepted

Solution code:
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    #print(dp)
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        # Copyright (c) 2016 Carl Ekerot
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        # Maps each subset of the nodes to the cost to reach that subset, as well
        # as what node it passed before reaching this subset.
        # Node subsets are represented as set bits.
        C = {}
        dp = defaultdict(int)

        # Set transition cost from initial state
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        # Iterate subsets of increasing length and store intermediate results
        # in classic dynamic programming manner
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                # Set bits for all nodes in this subset
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                # Find the lowest cost to get to this subset
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        # We're interested in all bits but the least significant (the start state)
        bits = (2 ** n - 1) - 1

        # Calculate optimal cost
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        # Backtrack to find full path
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        # Add implicit start state
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    #print(dp)
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    loop = 2**M
    dp = [inf]*loop
    dp[0] = 0
    cnt = Counter(A)
    L = [0]*loop
    #print(imos)
    for i in range(loop):
        for j in range(M):
            if i&(1<<j)==(1<<j):
                continue
            next = i|(1<<j)
            if L[next]==0:
                L[next] = L[i]+cnt[j]
            cur = imos[j][L[next]] - imos[j][L[i]]
            if dp[next]>dp[i] + cur:
                dp[next] = dp[i] + cur
    ans = dp[-1]
    #print(L)
    print(ans)
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        #print(que,cur,L)
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    #print(que)
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    def dijkstra_2(edge_adj, node, start):
        # node<=2000くらい
        # edge_adj[node][to] = [cost]
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    V = [[inf]*N for _ in range(N)]
    ans = []
    for _ in range(K):
        A = LI()
        s = A[1]-1
        t = A[2]-1
        if A[0]==1:
            if V[s][t] <= A[3]:
                continue
            V[s][t] = A[3]
            V[t][s] = A[3]
        else:
            dist = dijkstra_2(V,N,s)
            ans.append(dist[t])
    for v in ans:
        if v==inf:
            print(-1)
            continue
        print(v)
    return

def JOI15_E():
    def bfs(n, E, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [inf] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        que = deque()
        for e in E:
            e -=1
            W[e] = 0
            que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] > nowW + 1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M, K, S = LI()
    P, Q = LI()
    C = [I()for _ in range(K)]
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t = LI()
        s -= 1
        t -= 1
        V[s].append(t)
        V[t].append(s)
    L = bfs(N,C,V)
    #print(L)
    cost = [[]for _ in range(N)]
    for i in range(N):
        for v in V[i]:
            if L[v]==0:
                continue
            elif L[v]<=S:
                cost[i].append((v,Q))
            else:
                cost[i].append((v,P))
    di = Dijkstra(cost)
    ans = di.dist
    #print(cost)
    if L[-1]<=S:
        print(ans[N-1]-Q)
    else:
        print(ans[N-1]-P)
    return

def JOI13_E():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [inf] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == inf:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    def dijkstra_2(edge_adj, node, start):
        # node<=2000くらい
        # edge_adj[node][to] = [cost]
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    C = [[]for _ in range(N)]
    V = [[]for _ in range(N)]
    for i in range(N):
        C[i] = LI()
    for i in range(K):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    costV = [[inf]*N for _ in range(N)]
    for i in range(N):
        L = bfs(N,i,V)
        c = C[i][0]; l = C[i][1]
        for j in range(N):
            if i==j:
                continue
            if L[j]<=l:
                costV[i][j] = c
    dist = dijkstra_2(costV,N,0)
    ans = dist[N-1]
    #print(costV)
    print(ans)
    return

def ABC12_D():
    def warshall_floyd(n, d):
        # d[i][j]: iからjへの最短距離
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N, M = LI()
    V = [[inf]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for _ in range(M):
        a, b, t = LI()
        a -= 1
        b -= 1
        V[a][b] = t
        V[b][a] = t
    L = warshall_floyd(N,V)
    #print(L)
    ans = inf
    for i in range(N):
        cur = max(L[i])
        ans = min(ans,cur)
    print(ans)
    return

def ABC79_D():
    def warshall_floyd(n, d):
        # d[i][j]: iからjへの最短距離
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    H, W = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    L = warshall_floyd(10,C)
    #print(L)
    ans = 0
    for a in A:
        for i in a:
            if i>=0:
                ans += L[i][1]
    print(ans)
    return

def JOIgassyuku10_3():
    N, M, K = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b, c = LI()
        a -= 1
        b -= 1
        V[a].append((b,c))
        V[b].append((a,c))


    return

def ABC74_D():
    def warshall_floyd(n, d):
        # d[i][j]: iからjへの最短距離
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N = I()
    A = [LI() for _ in range(N)]
    dist = warshall_floyd(N,copy.deepcopy(A))
    shortest_path = 0
    for i in range(N):
        for j in range(N):
            if i==j:
                continue
            if dist[i][j]<A[i][j]:
                print(-1)
                return
            if dist[i][j]>A[i][j]:
                continue
            flag = True
            for k in range(N):
                if i==k or j==k:
                    continue
                judge = (dist[i][k]+dist[k][j])-dist[i][j]
                if judge==0:
                    flag = False
            if flag:
                shortest_path += A[i][j]
    ans = shortest_path//2
    print(ans)
    return

def ABC65_D():
    class Kruskal_UnionFind():
        # 無向グラフであるという前提に注意
        def __init__(self, N):
            self.edges = []
            self.rank = [0] * N
            self.par = [i for i in range(N)]
            self.counter = [1] * N

        def add(self, u, v, d):
            """
            u = from, v = to, d = cost
            """
            self.edges.append([u, v, d])

        def find(self, x):
            if self.par[x] == x:
                return x
            else:
                self.par[x] = self.find(self.par[x])
                return self.par[x]

        def unite(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                z = self.counter[x] + self.counter[y]
                self.counter[x], self.counter[y] = z, z
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

        def size(self, x):
            x = self.find(x)
            return self.counter[x]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def Kruskal(self):
            """
            return: 最小全域木のコストの和
            """
            edges = sorted(self.edges, key=lambda x: x[2])  # costでself.edgesをソートする
            res = 0
            for e in edges:
                if not self.same(e[0], e[1]):
                    self.unite(e[0], e[1])
                    res += e[2]
            return res
    N = I()
    X = []
    for i in range(N):
        a, b = LI()
        X.append((a,b))
    P = defaultdict(set)
    for i,x in enumerate(X):
        P[x] = i
    graph = Kruskal_UnionFind(N + 1)

    X.sort(key=lambda x:x[0])
    for i in range(N-1):
        if X[i+1][0]-X[i][0]>abs(X[i+1][1]-X[i][1]):
            continue
        r = X[i+1][0]-X[i][0]
        graph.add(P[X[i]], P[X[i+1]], r)

    X.sort(key=lambda x:x[1])
    for i in range(N-1):
        if X[i+1][1]-X[i][1]>abs(X[i+1][0]-X[i][0]):
            continue
        r = X[i+1][1]-X[i][1]
        graph.add(P[X[i]], P[X[i+1]], r)

    ans = graph.Kruskal()
    print(ans)
    return

def ABC84_D():
    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

    def like_2017(x):
        if is_prime(x) and is_prime(x//2+1):
            return True
        return False

    Q = I()
    maxX = 10**5
    imos = [0]*(maxX+1)
    for i in range(maxX+1):
        if like_2017(i) and i!=2:
            imos[i] = imos[i-1] + 1
        else:
            imos[i] = imos[i - 1]
    L = [LI()for _ in range(Q)]
    ans = []
    for l,r in L:
        cur = imos[r]-imos[l-1]
        ans.append(cur)
    for v in ans:
        print(v)
    return




def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    #print(L)
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        #print(ans)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

import gc
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC84_D()
"""
"""

Submission status: Accepted

Solution code:
import bisect
pp = [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]
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    print(bisect.bisect_right(pp,r)-bisect.bisect_left(pp,l))

Submission status: Accepted

Solution code:
import bisect

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

primes = eratosthenes(10**5)
Primes = set(primes)
pp = []
for i in primes:
    if (i+1)//2 in Primes:
        pp.append(i)
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    print(bisect.bisect_right(pp,r)-bisect.bisect_left(pp,l))

Submission status: Accepted

Solution code:
import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, math.ceil(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True


# 素数を表にする
primetable = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if is_prime(i):
        primetable[i] = 1

# 2017に似た数を表にする
like2017table = [ 0 for i in range(100001) ]
for i in range(2, 100001):
    if primetable[i] == 1 and \
        primetable[(i+1)//2] == 1:
        like2017table[i] = 1

# 累積和を計算する
cumsum = [ 0 for i in range(100001) ]
currentSum = 0
for i in range(2, 100001):
    currentSum += like2017table[i]
    cumsum[i] = currentSum

n = int(input())
queries = []
for _ in range(n):
    queries.append(list(map(int, input().split())))

for query in queries:
    begin = query[0]
    end = query[1]
    ans = cumsum[end] - cumsum[begin-1]
    print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

q = int(input())

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

m_r = max(r)

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

acc_table = list(accumulate(table))

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

Submission status: Accepted

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

q = int(input())

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

m_r = max(r)

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

c_table = list(accumulate(table))

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

Submission status: Accepted

Solution code:
from itertools import accumulate


def gen_primes(n: int) -> set:
    if n < 2:
        return set()
    is_prime = [True] * n
    for i in range(3, n, 2):
        if is_prime[i]:
            is_prime[i * i:: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return {2} | {i for i in range(3, n, 2) if is_prime[i]}


if __name__ == "__main__":
    max_n = 10 ** 5 + 1
    primes = gen_primes(max_n)

    is_like_2017 = [True if i in primes and (i + 1) // 2 in primes else False for i in range(max_n)]
    sum_is_like_2017 = tuple(accumulate(is_like_2017))

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

Submission status: Accepted

Solution code:
def gen_is_prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    # return [i for i in range(n + 1) if is_prime[i]]
    return is_prime


if __name__ == "__main__":
    max_n = 10 ** 5
    is_prime = gen_is_prime(max_n)

    is_like_2017 = [False] * (max_n + 1)
    for i in range(max_n + 1):
        if is_prime[i] and is_prime[(i + 1) // 2]:
            is_like_2017[i] = True

    sum_is_like_2017 = [0] * (max_n + 2)
    for i in range(max_n + 1):
        sum_is_like_2017[i + 1] = sum_is_like_2017[i] + is_like_2017[i]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

Q = int(input())
lr = []
l = []
r = []
for _ in range(Q):
    lr.append([int(x) for x in input().split()])
    l.append(lr[-1][0])
    r.append(lr[-1][1])

import math

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

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

    return True

minl, maxr = min(l), max(r)
cumsum = [0] * (maxr + 1)

for i in range(1, maxr + 1, 2):
    if is_prime(i) and is_prime((i + 1) // 2) and i > 1:
        cumsum[i] = cumsum[i - 2] + 1
    elif i > 1:
        cumsum[i] = cumsum[i - 2]

for j in lr:
    l, r = j
    if l == 1:
        print(cumsum[r])
    else:
        print(cumsum[r] - cumsum[l - 2])

Submission status: Accepted

Solution code:
q_num = int(input())
q_l = [tuple(map(int, input().split())) for _ in range(q_num)]

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

# エラトステネスの篩
for i in range(2, int(len(table) ** 0.5)):
    if table[i] == 0:
        continue
    step = i * 2
    while True:
        if step >= len(table):
            break
        table[step] = 0
        step += i

# 2017 like number table
table_like_n = [0] * len(table)
for i in range(1, len(table_like_n)):
    if i % 2 == 0:
        continue
    if table[i] == 1 and table[(i+1)//2] == 1:
        table_like_n[i] = 1

# 累積和の作成
accum_sum = [0] * (len(table_like_n) + 1)
for i in range(len(table_like_n)):
    accum_sum[i+1] = accum_sum[i] + table_like_n[i]

# クエリの分析
for l, r in q_l:
    print(accum_sum[r+1]-accum_sum[l])

Submission status: Accepted

Solution code:
import math
import bisect
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

prime=set([2])
for i in range(3,100001):
    if i%2!=0 and is_prime(i):
        prime.add(i)

sim_prime=[]
for p in prime:
    if (p+1)//2 in prime:
        sim_prime.append(p)
sim_prime.sort()


q=int(input())
ans_list=[]
for i in range(q):
    l,r=map(int,input().split())
    l_idx=bisect.bisect_left(sim_prime,l)
    r_idx=bisect.bisect_left(sim_prime,r+1)
    ans_list.append(r_idx-l_idx)

for g in range(len(ans_list)):
    print(ans_list[g])

Submission status: Accepted

Solution code:
import math
import bisect
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

prime=set([2])
for i in range(3,100001):
    if i%2!=0 and is_prime(i):
        prime.add(i)

sim_prime=[]
for p in prime:
    if (p+1)//2 in prime:
        sim_prime.append(p)
sim_prime.sort()


q=int(input())
ans_list=[]
for i in range(q):
    l,r=map(int,input().split())
    l_idx=bisect.bisect_left(sim_prime,l)
    r_idx=bisect.bisect_left(sim_prime,r)
    if sim_prime[min(r_idx,len(sim_prime)-1)]==r:
        r_idx+=1
    ans_list.append(r_idx-l_idx)

for g in range(len(ans_list)):
    print(ans_list[g])