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())
A = []
B = []
for i in range(Q):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
    
def sieve(N):
    p = 0
    prime = []
    is_prime = [1 for _ in range(N + 1)]
    is_prime[0], is_prime[1] = 0, 0
    for i in range(2, N + 1):
        if is_prime[i]:
            p += 1
            temp = i
            prime.append(i)
            while(temp <= N):
                is_prime[temp] = 0
                temp += i
            is_prime[i] = 1
    return is_prime

p_list = sieve(10 ** 5 + 10)
acc = [0, 0]
for i in range(3, 10 ** 5 + 1, 2):
    if p_list[i] and p_list[(i + 1) // 2]:
        acc.append(acc[-1] + 1)
    else:
        acc.append(acc[-1])
for i in range(Q):
    print(acc[(B[i] + 1) // 2] - acc[(A[i] + 1) // 2 - 1])

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

p = [True] * (10 ** 5 + 1)
p[0] = p[1] = False
for i in range(2, 10 ** 5 + 1):
    for j in range(2 * i, 10 ** 5 + 1, i):
        p[j] = False

pp = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    pp[i] = int(p[i] and p[(i + 1) // 2]) + pp[i - 1]

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

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

p = [True] * (10 ** 5 + 1)
p[0] = p[1] = False
for i in range(2, 10 ** 5 + 1):
    for j in range(2 * i, 10 ** 5 + 1, i):
        p[j] = False

pp = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    pp[i] = int(p[i] and p[(i + 1) // 2]) + pp[i - 1]

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

Solution (Python):
MAX_INT = 10**5+1
primes = [True] * (10**5+1)
primes[0], primes[1] = False, False
for i in range(2, int(MAX_INT**0.5)+1):
  if primes[i]:
    for j in range(i*2, MAX_INT, i):
      primes[j] = False

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

for i in range(1, 10**5+1):
  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 make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    j = (i + 1) // 2
    if prime_table[i] == i and prime_table[j] == j:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

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

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

Solution (Python):

def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    j = (i + 1) // 2
    if prime_table[i] == i and prime_table[j] == j:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
print('\n'.join(str(i) for i in result))

Solution (Python):
import bisect
q = int(input())
LR = (tuple(map(int,input().split())) for i in range(q))
ans = []
sosuu = [2]
A = 100000
for L in range(3, A, 2): 
    for L2 in sosuu:
        if L % L2 == 0:
            break 
    else: 
        sosuu.append(L)
        if (L+1)/2 in sosuu:
          ans.append(L)
for lr in LR:
  print(bisect.bisect_right(ans,lr[1]) - bisect.bisect_left(ans,lr[0]))

Solution (Python):
import bisect
q = int(input())
LR = [tuple(map(int,input().split())) for i in range(q)]
ans = []
sosuu = set([2])
A = 100000
for L in range(3, A, 2): 
    for L2 in sosuu:
        if L % L2 == 0:
            break 
    else: 
        sosuu.add(L)
        if (L+1)/2 in sosuu:
          ans.append(L)
for lr in LR:
  print(bisect.bisect_right(ans,lr[1]) - bisect.bisect_left(ans,lr[0]))

Solution (Python):
import bisect
q = int(input())
LR = [tuple(map(int,input().split())) for i in range(q)]
ans = []
sosuu = [2]
A = 100000
for L in range(3, A, 2): 
    for L2 in sosuu:
        if L % L2 == 0:
            break 
    else: 
        sosuu.append(L)
        if (L+1)/2 in sosuu:
          ans.append(L)
for lr in LR:
  print(bisect.bisect_right(ans,lr[1]) - bisect.bisect_left(ans,lr[0]))

Solution (Python):
q = int(input())
is_prime = [1] * (10**5 + 1)
is_prime[0] = 0
is_prime[1] = 0
for i in range(2, 10**5+1):
    if is_prime[i] == 1:
        for j in range(i+i, 10**5+1, i):
            is_prime[j] = 0
ls = [0]
for i in range(1, 10**5+1):
    if is_prime[i] == 1 and is_prime[(i+1)//2] == 1:
        ls.append(ls[i-1]+1)
    else:
        ls.append(ls[i-1])
for i in range(q):
    l, r = map(int, input().split())
    print(ls[r] - ls[l-1])

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

    return is_prime


q = int(input())

p = eratosthenes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if p[i] and p[(i+1)//2]:
        l[i] = 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

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

for v in res:
    print(v)

Solution (Python):
from bisect import bisect_left


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

    return is_prime


q = int(input())

p = eratosthenes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if p[i] and p[(i+1)//2]:
        l[i] = 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

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

for v in res:
    print(v)

Solution (Python):
from bisect import bisect_left


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]]


def is_similar(n):
    pos = bisect_left(p, n)
    if pos < len(p) and p[pos] == n:
        return True
    else:
        return False


q = int(input())

p = primes(10 ** 5)
l = [0] * 10 ** 5
for i in range(3, 10 ** 5, 2):
    if is_similar(i) and is_similar((i+1)//2):
        l[i] += 1

sum_l = [0]
for v in l[1:]:
    sum_l.append(sum_l[-1] + v)

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

for v in res:
    print(v)

Solution (Python):


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


data = [0] * 10**5

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

cumulative_sum = [0] * 10**5
cumulative_sum[0] = data[0]
for i in range(10**5 - 1):
    cumulative_sum[i+1] += cumulative_sum[i] + data[i+1]


cumulative_sum = [0] + cumulative_sum

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

Solution (Python):

def make_prime_table(N):
    sieve = list(range(N + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, N + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    j = (i + 1) // 2
    if prime_table[i] == i and prime_table[j] == j:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
print('\n'.join(str(i) for i in result))

Solution (Python):

def make_prime_table(N):
    sieve = list(range(N + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, N + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
print('\n'.join(str(i) for i in result))

Solution (Python):

def make_prime_table(N):
    sieve = [0] * (N + 1)
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, N + 1):
        if sieve[i] != 0:
            continue
        sieve[i] = i
        for j in range(i * i, N + 1, i):
            if sieve[j] == 0:
                sieve[j] = i
    return sieve

max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

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

Solution (Python):













q = int(input())
n = 10**5+1
limit = int(n**0.5)
a = [i for i in range(3, n, 2)]
prime = [2]
while True:
  p = a[0]
  if limit <= p:
    prime += a
    break
  prime.append(p)
  a = [j for j in a if j%p!=0]
  
pi = [0]*n
for i in range(len(prime)):
  ai = (prime[i]+1)//2
  if ai in prime:
    pi[prime[i]-1] = 1
    
s = [0]*n
s[0] = pi[0]
for i in range(len(pi)-1):
  s[i+1] = s[i] + pi[i+1]
s = [0,0] + s
for i in range(q):
  l, r = map(int, input().split())
  print(s[r+1]-s[l])

Solution (Python):
import numpy as np
L = 10**5


def main():
    is_prime = np.full(L+1, True, dtype=bool)
    is_prime[0:2] = False
    for i in range(2, int(np.sqrt(L))+1):
        if is_prime[i] == False:
            continue
        is_prime[i+i:L+1:i] = False
    
    
    is_like_2017 = np.full(L+1, False, dtype=bool)

    for i in range(2, L+1):
        if 2*i-1 > L:
            break
        if is_prime[i]:
            is_like_2017[2*i-1] = True

    is_like_2017[2] = False

    is_like_2017 = np.logical_and(is_prime, is_like_2017)
    accumulate = np.cumsum(is_like_2017)

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


if __name__ == "__main__":
    main()

Solution (Python):
flag = [False]*100001
c = [0]*100002
n = int(input())

for i in range(2,100000):
    if(not(flag[i])):
        for j in range(i+i,100000,i):
            flag[j] = True

for i in range(3,100000,2):
    if(not(flag[i]) and not(flag[(i+1)//2])):
        c[i]+=1
for i in range(3,100000):
    c[i]+=c[i-1]

while(n):
    n-=1
    l,r = map(int,input().split())
    print(c[r]-c[l-1])

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

n = 10 ** 5
memo = [1] * (n+1)

for i in range(2, n):
  for j in range(2, n):
    if i * j > n:
      break
    memo[i*j] = 0
memo2 = memo[:]
memo2[1] = 0
for x in range(n+1):
  if x % 2 == 0 or memo[(x+1) // 2] == 0:
    memo2[x] = 0
  
c = [0]

for x in memo2[1:]:
  c.append(c[-1]+x)

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

Solution (Python):
Q = int(input())
l = []
r = []
for i in range(Q):
    a, b = map(int, input().split())
    l.append(a)
    r.append(b)
    
x =[True]*((10**5)+1)
x[0] = False
x[1] = False
s = [0, 0, 0]

for i in range(4, (10**5)+1, 2):
    x[i] = False

for j in range(3, (10**5)+1):
    if x[j] == False:
        s.append(s[-1])
        continue
    for k in range(2*j, (10**5)+1, j):
        x[k] = False
    if x[(j+1)//2] == True:
        s.append(s[-1]+1)
    else:
        s.append(s[-1])

for i in range(Q):
    print(s[r[i]]-s[l[i]-1])

Solution (Python):
Q=  int(input())
dp = [False]*(100001)
for i in range(2,100001):
    if not dp[i]:
        for j in range(2*i,100001,i):
            dp[j] = True
A = []
for i in range(3,100001):
    if not dp[i] and not dp[(i+1)//2]:
        A.append(i)
from bisect import bisect_left, bisect_right
queries = []
for _ in range(Q):
    l,r = map(int,input().split())
    queries.append([l,r])
for l,r in queries:
    idl = bisect_left(A,l)
    idr = bisect_right(A,r)
    print(idr-idl)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter




q=int(input())
def primes(n):
    m=int(pow(n,0.5))
    is_prime=[True]*(n+1)
    is_prime[0]=False
    is_prime[1]=False
    for i in range(2,m+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]]
s=set(primes(10**5))
count=[0]*(10**5+1)
count[1]=0
count[2]=0
for i in range(3,10**5+1):
    if i in s and (i+1)//2 in s:
        count[i]=count[i-1]+1
    else:
        count[i]=count[i-1]
for i in range(q):
    l,r = map(int,input().split())
    print(count[r]-count[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]]
dp=[0]*(10**5+1)
bp=[0]*(10**5+1)
for i in primes(10**5):
  dp[i]=1
for i in range(1,10**5+1):
  bp[i]+=bp[i-1]
  if i%2==0:
    continue
  if dp[(i+1)//2]==1 and dp[i]==1:
    bp[i]+=1
Q=int(input())
for _ in range(Q):
  l,r=map(int,input().split())
  print(bp[r]-bp[l-1])

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

Solution (Python):

q = int(input())
lr = []
for i in range(q):
    lr.append([int(j)-1 for j in input().split()])

import math
def test_div(index):
    if index < 2:
        return 0
    elif index == 2:
        return 1
    max = math.ceil(math.sqrt(index))+1
    ls = []
    for i in range(2,max):
        if index % i == 0:
            return 0
    return 1

primes = [2]

import time
st = time.time()

ls = []
for i in range(100000):
    ls.append(test_div(i+1))
ls_like = [0] * 100000
for i in range(100000):
    if ls[i]:
        if ls[(i+2)//2-1]:
            ls_like[i] = 1
        else:
            ls_like[i] = 0
    else:
        ls_like[i] = 0

ls_acc = [0]
for i in range(100000):
    ls_acc.append(ls_acc[-1] + ls_like[i])




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

Solution (Python):
def main():
    
    MAX_NUM = 101010
    is_prime = [1 for _ in range(MAX_NUM)]
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, MAX_NUM):
        if not is_prime[i]:
            continue
        for j in range(i * 2, MAX_NUM, i):
            is_prime[j] = 0

    
    like2017 = [0 for _ in range(MAX_NUM)]
    for i in range(MAX_NUM):
        if i % 2 == 0:
            continue
        if is_prime[i] and is_prime[(i + 1) // 2]:
            like2017[i] = 1

    
    cumsum = [0 for _ in range(MAX_NUM + 1)]
    for i in range(MAX_NUM):
        cumsum[i + 1] = cumsum[i] + like2017[i]

    Q = int(input())
    L = [None] * Q
    R = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        L[i] = l
        R[i] = r

    for i in range(Q):
        print(cumsum[R[i] + 1] - cumsum[L[i]])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

def era(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 = i()
primes = []
l1 = era(100000)
for l in range(len(l1)):
    if l1[l] == 1:
        primes.append(l)
l2 = []
for l in primes:
    if (l+1)//2 in primes:
        l2.append(l)
for i in range(Q):
    l,r = I()
    print(bisect.bisect_right(l2,r)-bisect.bisect_left(l2,l))

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

def era(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 = i()
primes = []
l1 = era(100000)
for l in range(len(l1)):
    if l1[l] == 1:
        primes.append(l)
l2 = []
for l in primes:
    if (l+1)//2 in primes:
        l2.append(l)
for i in range(Q):
    l,r = I()
    print(bisect.bisect_right(l2,r)-bisect.bisect_left(l2,l))

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7

judge = [0 for i in range(10**5+1)]

n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):    
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)
for num in primes:
    judge[num] = 1
area = [0 for i in range(10**5+1)]
for num in primes[1:]:
    if judge[(num+1)//2] == 1:
        area[num] = 1
Area = [0]
for num in area:
    Area.append(Area[-1]+num)
def sumArea(l,r):
    return Area[r] - Area[l]
q = ir()
for i in range(q):
    l,r = lr()
    print(sumArea(l,r+1))

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

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

def main(n):
    return 1 if is_prime(n) and is_prime((n + 1) // 2) else 0

MAX = 10 ** 5 + 100
A = [main(i) for i in range(MAX)]

acc = [0] * (MAX + 1)
for i in range(MAX):
    acc[i + 1] = acc[i] + A[i]

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

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate 

from collections import deque,defaultdict,Counter
import decimal
import re











import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
is_prime = [1] * (10**5 + 1)
is_prime[0] = 0
is_prime[1] = 0
for i in range(2,10**5+1):
    if is_prime[i]:
        for j in range(i*2,10**5+1,i):
            is_prime[j] = 0
for i in range(10**5,1,-1):
    if is_prime[i]:
        if is_prime[(i+1)//2]:
            pass
        else:
            is_prime[i] = 0
is_prime = list(accumulate(is_prime))
for q in range(I()):
    l,r = readInts()
    l -= 1
    print(is_prime[r] - is_prime[l])

Solution (Python):
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, 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
    for i in range(len(is_prime)):
        if is_prime[i]: ass.append(i)
    return ass

d = primes(10**5)
d2017 = []
for i in d:
    if i > 10**5: break
    if (i+1)//2 in d:
        d2017.append(i)

import bisect
q = int(input())
ans = 0
for _ in range(q):
    l, r = map(int, input().split())
    index_l = bisect.bisect_left(d2017, l-1)
    index_r = bisect.bisect_right(d2017, r)
    print(index_r-index_l)

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

l = [0 for i in range(10**6)] 

for i in range(1,10**5+1):
  if i%2==0:
    continue
  else:
    if prime(i):
      if prime((i+1)//2):
        l[i] = 1
l1 = list(accumulate(l))
q = int(input())
for i in range(q):
  l,r = map(int,input().split())
  print(l1[r]-l1[l-1])

Solution (Python):
Q=int(input())
l=[0]*100001
l2=[0]*100001
def d(n):
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
for i in d(100000):
   l[i]=1
for i in range(3,100001):
   if l[i] == 1:
      if l[(i+1)//2]==1:
         l2[i]=1
for i in range(1,100001):
   l2[i]+=l2[i-1]
qe=[list(map(int,input().split())) for i in range(Q)]
for i in qe:
   print(l2[i[1]]-l2[i[0]-1])

Solution (Python):
data = sorted(list(range(10**5+1)))
prime_bool = [True]*(10**5+1)
prime_bool[0] = False
prime_bool[1] = False
for i in range(2, len(data)):
  p = data[i]
  if prime_bool[p]:
    k = 2
    while k*p <= 10**5:
      prime_bool[k*p] = False
      k += 1

count_list = [0]*(10**5+1)
for i in range(1, 10**5+1):
  count_list[i] = count_list[i-1]
  if prime_bool[i] and prime_bool[(i+1)//2]:
    count_list[i] += 1

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

Solution (Python):
Q = int(input())
l, r = [], []
for i in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
max_r = max(r)

is_sosu = [1] * (max_r + 1)
is_sosu[0] = is_sosu[1] = 0
for i in range(2, max_r + 1):
    if is_sosu[i]:
        for j in range(i * i, max_r + 1, i):
            is_sosu[j] = 0

sums = [0] * (max_r + 1)
for i in range(1, max_r + 1):
    if is_sosu[i] and is_sosu[(i + 1) // 2]:
        sums[i] = sums[i - 1] + 1
    else:
        sums[i] = sums[i - 1]

for i in range(Q):
    print(sums[r[i]] - sums[l[i] - 1])

Solution (Python):
q=int(input())
l=[]
r=[]
for i in range(q):
    lr=list(map(int,input().split()))
    l.append(lr[0])
    r.append(lr[1])
n=sorted(r,reverse=True)[0]
prime=[True]*(n+1)
prime[0]=False
prime[1]=False
for i in range(2,int(n**(0.5))+1):
    if prime[i]:
        for j in range(i*2,n,i):
            prime[j]=False
a=[0]*(n+1)
for i in range(n+1):
    if i%2==0:
        continue
    if prime[i] and prime[(i+1)//2]:
        a[i]=1
s=[0]*(n+2)
for i in range(n+1):
    s[i+1]=s[i]+a[i]
for i in range(q):
        print(s[r[i]+1]-s[l[i]])

Solution (Python):

from itertools import accumulate

def isPrime(x):
    if x == 2: flag = True
    else:
        flag = True
        if x % 2 == 0:
            flag = False
        
        i = 3
        while i**2 <= x and flag == True:
            if x % i == 0:
                flag = False
            else:
                i += 2
    return True if flag == True else False

q = int(input())
arr = []
max_v = 0
for i in range(q):
    l,r = map(int, input().split())
    arr.append((l,r))
    max_v = max(max_v, r)

res_arr = [0]*(max_v+1)
for i in range(3,max_v+1,2):
    v1, v2 = i, (i+1)//2
    if isPrime(v1) == True and isPrime(v2) == True:
        res_arr[i] = 1

cumsum = list(accumulate(res_arr))


for i in range(q):
    l,r = arr[i][0], arr[i][1]
    print(cumsum[r] - cumsum[l-1])

Solution (Python):
MAX = 10 ** 5
def sieve(n):
    f = [False] * (n + 1)
    res = []
    for i in range(2, n+1):
        if f[i]:
            continue
        res.append(i)
        for j in range(2 * i, n+1, i):
            f[j] = True
    return res

pn = sieve(MAX)
acc = [0] * (MAX + 1)
for p in pn:
    if p % 2 == 1 and (p + 1) // 2 in pn:
        acc[p] = 1
for i in range(2, MAX+1):
    acc[i] += acc[i-1]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(acc[r] - acc[l-1])

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

Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]
p = prime_list(100010)
s = []
s.append(0)
for i in range(100001):
    if (i%2 == 1) and i in p and (i+1)//2 in p:
        s.append(s[i]+1)
    else:
        s.append(s[i])
for lr in LR:
    print(s[lr[1]+1]-s[lr[0]])

Solution (Python):
flag = [False]*100001
c = [0]*100002
n = int(input())

for i in range(2,100000):
    if(not(flag[i])):
        for j in range(i+i,100000,i):
            flag[j] = True
for i in range(3,100000,2):
    if(not(flag[i]) and not(flag[(i+1)//2])):
        c[i]+=1
for i in range(3,100000):
    c[i]+=c[i-1]

while(n):
    n-=1
    l,r = map(int,input().split())
    print(c[r]-c[l-1])

Solution (Python):
q=int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
def primesFactraizar(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]]
primes = primesFactraizar(10**5+1)

cumSum = [0]*(10**5+1)
tmp = 0
for i in range(10**5+1):
    if i in primes and (i+1)//2 in primes:
        tmp += 1 
    cumSum[i] = tmp


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

Solution (Python):
import numpy as np
MAXX = 10**5 + 5

isprime = np.ones(MAXX, dtype=bool)
count = np.zeros(MAXX, dtype=int)


isprime[0] = isprime[1] = False
for i in range(2, MAXX):
    if isprime[i]:
        isprime[2*i::i] = False

for i in range(1, MAXX):
    if isprime[i] and isprime[(i+1)>>1]:
        count[i] = 1


for i in range(1, MAXX):
    count[i] += count[i-1]


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

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


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

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

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

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

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

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 = []
    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]

prime=[0]*(10**5+1)
prime_lst=get_sieve_of_eratosthenes(10**5)
for i in prime_lst:
    prime[i]+=1

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

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

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

Solution (Python):
import bisect

sosu=set()
nums=[1]*(10**5+1)
for i in range(2, 10**5+1):
  if nums[i]==1:
    sosu.add(i)
    j=i
    while j<10**5+1:
      nums[j]=0
      j+=i
      
nums=[x for x in range(3, 2*10**5+1, 2) if x in sosu and (x+1)//2 in sosu]

Q=int(input())
for _ in range(Q):
  l, r=map(int, input().split())
  a=bisect.bisect_left(nums, l)
  b=bisect.bisect_right(nums, r+1)
  print(b-a)

Solution (Python):
from itertools import accumulate
Q = int(input())
m = 0
ls = []
for i in range(Q):
    l, r = map(int, input().split())
    m = max(m, max(l, r))
    ls.append((l, r))

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

a = sieve_eratosthenes(m)
b = [0 for i in range(m+1)]
for i in range(2, m+1):
    if i%2 == 1 and a[i] == 1 and a[(i+1)//2] == 1:
        b[i] = 1
c = list(accumulate(b))
for l, r in ls:
    print(c[r] - c[l-1])