Problem:
 Score : 400 points    Problem Statement We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.  You are given Q queries.  In the i -th query, given two odd numbers l_i and r_i , find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i .      Constraints  1≤Q≤10^5  1≤l_i≤r_i≤10^5  l_i and r_i are odd.  All input values are integers.         Input Input is given from Standard Input in the following format:  Q  l_1  r_1  :  l_Q  r_Q       Output Print Q lines. The i -th line (1≤i≤Q) should contain the response to the i -th query.        Sample Input 1 1
3 7      Sample Output 1 2   3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.  5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.  7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.   Thus, the response to the first query should be 2 .       Sample Input 2 4
13 13
7 11
7 11
2017 2017      Sample Output 2 1
0
0
1  Note that 2017 is also similar to 2017.       Sample Input 3 6
1 53
13 91
37 55
19 51
73 91
13 49      Sample Output 3 4
4
1
1
1
2

Solution (Python):
from math import ceil














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

p_list = primes(10**5)
p_set = set(p_list)
cnt = 0
a = [0] * 10**5
for i in range(10**5):
    if i in p_set:
        if ceil(i/2) in p_set:
            cnt += 1
            
    a[i] = cnt



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

Solution (Python):
Q = int(input())
lr = [tuple(map(int, input().split())) for i in range(Q)]


def primes(n):
    ret = []
    A = [i for i in range(2, n+1)]
    k = 0
    s = n**0.5
    while(k < s):
        ret.append(A[0])
        k = A[0]
        A = [x for x in A if x % k]
    ret += A
    return ret


prime = primes(10**5)

prime_s = set(prime)
t = [0]*(10**5 + 1)
for i in range(1, 10**5+1):
    if i in prime_s and (i+1)//2 in prime_s:
        t[i] = 1
for i in range(1, 10**5+1):
    t[i] = t[i] + t[i-1]

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

Solution (Python):
Q=int(input())
A=[0]
S=[0]*(10**5+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

def id2017(n):
  if is_prime(n) and is_prime((n+1)/2):
    return True
  else:
    False
count=0    
for i in range(1,10**5+1):
  if id2017(i) and i%2==1:
    count+=1
  S[i]=count
for i in range(Q):
  l,r=map(int, input().split())
  print(S[r]-S[l-1])

Solution (Python):

Q = int(input())
N = 10**5 + 1000

def getPrimes():
    isPrime = [True] * N
    isPrime[1] = False
    for i in range(2, N):
        if not isPrime[i]:
            continue
        for p in range(i + i, N, i):
            isPrime[p] = False
    return isPrime

isPrime = getPrimes()

A = [0] * (N)
for i in range(2, N):
    if i % 2 == 1 and isPrime[i] and isPrime[(i + 1) // 2]:
        A[i] = 1
accA = [0] * (N + 1)
for i, a in enumerate(A, start=0):
    accA[i] += accA[i - 1] + a

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

Solution (Python):

Q = int(input())
N = 10**5 + 1000

def getPrimes():
    isPrime = [True] * N
    isPrime[1] = False
    for i in range(2, N):
        if not isPrime[i]:
            continue
        for p in range(i + i, N, i):
            isPrime[p] = False
    return isPrime

isPrime = getPrimes()

A = [0] * (N)
for i in range(2, N):
    if i % 2 == 1 and isPrime[i] and isPrime[(i + 1) // 2]:
        A[i] = 1
accA = [0] * (N + 1)
for i, a in enumerate(A, start=0):
    accA[i] += accA[i - 1] + a

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

Solution (Python):
def main():
    from itertools import accumulate

    def Eratosthenes(x: int) -> set:
        from math import sqrt
        sup = int(x)
        primes = {i for i in range(2, sup+1)}
        for i in range(2, int(sqrt(sup+1))+1):
            if i in primes:
                mul = 2
                while i*mul <= sup:
                    primes.discard(i*mul)
                    mul += 1
        return primes
    P = Eratosthenes(10**5+5)
    A = [0]*(10**5+5)
    for i in range(3, 10**5+5):
        if i in P and (i+1)//2 in P:
            A[i] += 1
    S = list(accumulate(A))

    Q = int(input())
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    for le, ri in LR:
        print(S[ri] - S[le-1])


if __name__ == '__main__':
    main()

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]]
a=set(primes(100100))
b=[0]
for i in range(100100):
    f=0
    if i%2==1 and i in a and (i+1)//2 in a:
        f=1
    b.append(b[-1]+f)
q=int(input())
for i in range(q):
    a=list(map(int,input().split()))
    print(b[a[1]+1]-b[a[0]])

Solution (Python):
import bisect
def prime(n):
    max_=int(n**0.5)
    li=[i for i in range(2,n+1)]
    primes=[]
    while li[0]<=max_:
        primes.append(li[0])
        tmp=li[0]
        li=[i for i in li if i%tmp!=0]
    primes.extend(li)
    return primes
Q=int(input())
arr=prime(100000)
likenum=[]
n=len(arr)
for i in range(n):
    lik=(arr[i]+1)//2
    x=bisect.bisect_left(arr,lik)
    if(x<n and arr[x]==(lik)):
        likenum.append(arr[i])
for i in range(Q):
    L,R=map(int,input().split())
    r=bisect.bisect_left(likenum,R)
    l=bisect.bisect_left(likenum,L)
    if(r<len(likenum) and likenum[r]==R):
        r+=1
    print(r-l)

Solution (Python):
q = int(input())
lr = [list(map(int,input().split()))for _ in range(q)]
maxr = 0
for i in range(q):
    maxr = max(maxr,lr[i][1])
res = 0
cnt = [0]*(maxr+3)
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]]
x = primes(maxr+1)
for i in range(1,maxr+1):
    if i%2 == 0:
        cnt[i] = res
        continue
    if i in x and (i+1)//2 in x:
        res+=1

    cnt[i] = res
for i in range(q):
    l = lr[i][0]
    r = lr[i][1]
    print(cnt[r]-cnt[l-1])

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

fact=[True]*(10**5+1)
fact[0]=False
fact[1]=False

num=[0]*(10**5+1)
cur=0
for i in range(len(fact)):
  if fact[i]:
    for j in range(i*2,len(fact),i):
      fact[j]=False
    if fact[(i+1)//2]:
      cur+=1
  num[i]=cur
      
for i in range(Q):
  l,r=map(int,input().split())
  print(num[r]-num[l-1])

Solution (Python):
def is_prime(n):
    result = True
    i = 2
    while i * i <= n:
        if n % i == 0:
            result = False
            break
        i += 1
    if n == 1:
        result = False
    return result


def main():
    q = int(input())
    max_num = 10 ** 5
    count_num = [0 for _ in range(max_num + 1)]
    is_prime_num = [False for _ in range(max_num + 1)]
    count_num[3] = 1
    is_prime_num[3] = True
    for i in range(4, max_num + 1):
        count_num[i] = count_num[i - 1]
        if i % 2:
            if is_prime(i):
                is_prime_num[i] = True
                count_num[i] = count_num[i - 1]
                if is_prime_num[(i + 1) // 2]:
                    count_num[i] += 1
    for _ in range(q):
        l, r = map(int, input().split())
        print(count_num[r] - count_num[l - 1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

NN = 10 ** 5 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]

for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    min_factor[i] = i
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
        if min_factor[j] == -1:
            min_factor[j] = i
primescnt = [0 for _ in range(NN + 1)]
for i in range(3, NN + 1):
    primescnt[i] = primescnt[i - 1] + int(isprime[i] and isprime[(i + 1) // 2])
q = INT()
for _ in range(q):
    l, r = MAP()
    print(primescnt[r] - primescnt[l - 1])

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

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

    return True
n = 10**5+10
Q = inp()
ch = [False] * (n+5)
for i in range(1,n):
    if is_prime(i):
        ch[i] = True
table = [0] * (n+5)
for i in range(1,n):
    tmp = 0
    if i%2 and ch[i] and ch[(i+1)//2]:
        tmp = 1
    table[i] = table[i-1] + tmp
for _ in range(Q):
    a,b = inpl()
    print(table[b] - table[a-1])

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

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
prime_ls = primes(10**5)

csum = [0] * (10**5)
for i in range(1,10**5):
    if prime_ls[i]:
        if prime_ls[(i+1) // 2]:
            csum[i] = csum[i-1] + 1
        else:
            csum[i] = csum[i-1]
    else:
        csum[i] = csum[i-1]

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

Q = inp()
cnt = [False] * (10**5+10)
table = [False] * (10**5+10)
for i in range(1,10**5+5):
    cnt[i] = is_prime(i)
for i in range(1,10**5+5):
    table[i] = i%2 and cnt[i] and cnt[(i+1)//2]
res = [0] * (10**5+5)
for i in range(10**5+4):
    tmp = 1 if table[i] else 0
    res[i+1] = res[i] + tmp

for _ in range(Q):
    a,b = inpl()
    print(res[b+1] - res[a])

Solution (Python):
import math


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

q = int(input())
csum = [0, ]

i = 0
for m in range(1, 100000-1+1, 2):
    if prime_judge(m) and prime_judge(int((m+1)/2)):
        csum.append((csum[i]+1))
    else:
        csum.append(csum[i])
    i += 1

ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(csum[int(r/2)+1] - csum[int(l/2)])

for i in ans:
    print(i)

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

def main():
    def is_prime(n):
        if n == 1: return False
        for k in range(2, int(n**(1/2)) + 1):
            if n % k == 0:
                return False
        return True
    
    prime,now = [0],0
    for i in range(1,10**5+1):
        if i%2 == 1 and is_prime(i) and is_prime((i+1)//2):
            now += 1
        prime.append(now)
    
    N = int(input())
    for _ in range(N):
        a,b = map(int,input().split())
        print(prime[b]-prime[a-1])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from io import StringIO
import unittest
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 

    
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


def resolve():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]

    
    prime_list = set(primes(10 ** 5 + 1)) 

    """
    
    for l, r in lr:
        tmp = 0
        for i in range(l, r + 1):
            if i in prime_list and (i + 1)/2 in prime_list:
                tmp += 1
        print(tmp)
    """

    cum_2017 = [0, 0]
    
    tmp = 0
    for i in range(2, 10 ** 5 + 1, 1):
        if i in prime_list and (i + 1) / 2 in prime_list: 
            tmp += 1
            cum_2017.append(tmp)
        else:
            cum_2017.append(tmp)

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



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):
import sys
from io import StringIO
import unittest
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 

    
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


def resolve():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]

    
    prime_list = primes(10 ** 5 + 1) 

    """
    
    for l, r in lr:
        tmp = 0
        for i in range(l, r + 1):
            if i in prime_list and (i + 1)/2 in prime_list:
                tmp += 1
        print(tmp)
    """

    cum_2017 = [0, 0]
    
    tmp = 0
    for i in range(2, 10 ** 5 + 1, 1):
        if i in prime_list and (i + 1) // 2 in prime_list: 
            tmp += 1
            cum_2017.append(tmp)
        else:
            cum_2017.append(tmp)

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



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):
import sys
from io import StringIO
import unittest
import math

def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 

    
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


def resolve():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]

    
    prime_list = set(primes(10 ** 5 + 1)) 

    """
    
    for l, r in lr:
        tmp = 0
        for i in range(l, r + 1):
            if i in prime_list and (i + 1)/2 in prime_list:
                tmp += 1
        print(tmp)
    """

    cum_2017 = [0, 0]
    
    tmp = 0
    for i in range(2, 10 ** 5 + 1, 1):
        if i in prime_list and (i + 1) // 2 in prime_list: 
            tmp += 1
            cum_2017.append(tmp)
        else:
            cum_2017.append(tmp)

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



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """1
3 7"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4
13 13
7 11
7 11
2017 2017"""
        output = """1
0
0
1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
1 53
13 91
37 55
19 51
73 91
13 49"""
        output = """4
4
1
1
1
2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):
import itertools


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


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

L = tuple(itertools.accumulate(L))
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(L[(r + 1) // 2] - L[l // 2])

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

is_prime = [1 for i in range(n+1)]
is_prime[0], is_prime[1] = 0, 0


for i in range(2, n+1):
    if (not is_prime[i]):
        continue
    for j in range(i*2, n+1, i):
        is_prime[j] = 0

for i in range(2, n+1):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_prime[int((i+1)/2)]:
        a[i] = 1

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

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

Solution (Python):
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        if not is_prime[i]:
            continue

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

primes = sieve(10 ** 5)
likes = [primes[n] & primes[(n + 1) // 2] if n %  2 != 0 else False
         for n in range(10 ** 5)]
cumsum = [0] * (10 ** 5 + 1)
for i in range(10 ** 5):
    cumsum[i + 1] = cumsum[i] + int(likes[i])

for l, r in X:
    print(cumsum[r + 1] - cumsum[l])

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



def eratosthenes(n):
    is_prime = [1] * n
    is_prime[0] = 0
    prime=[]

    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = 2 * i
            while j <= n:
                is_prime[j - 1] = 0
                j += i
    for i in range(n):
        if is_prime[i]==1:
            prime.append(i+1)
    return prime



def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

q=int(input())
s= [list(map(int, input().split())) for i in range(q)]
v=eratosthenes(pow(10,5))
ans=[]
for i in range(len(v)):
    x=(v[i]+1)//2
    index = bisect.bisect_left(v, x)
    if v[index]==x:
        ans.append(v[i])

for i,j in s:
    r = bisect.bisect_left(ans, j+1)
    l = bisect.bisect_left(ans, i-1)
    print(r-l)

Solution (Python):
def Prime_number(x):
    
    
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

like_number=[0 for _ in range(10**5+1)]
cnt=0
for i in range(2,10**5+1):
    if i%2==0:
        continue
    if Prime_number(i) and Prime_number((i+1)//2):
        cnt+=1
    like_number[i]=cnt

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

Solution (Python):
Q = int(input())
lll = []
rrr = []
for i in range(Q):
    buff = [int(i) for i in input().split()]
    lll.append(buff[0])
    rrr.append(buff[1])

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)

Nmax = 10**5+5


isprime = [0 for i in range(Nmax)]
for i in get_sieve_of_eratosthenes(Nmax):
    isprime[i] = 1

cumulative_sum = [0 for i in range(Nmax)]
for i in range(1,Nmax):
    if i%2==1 and isprime[i]==1 and isprime[(i+1)//2]==1:
        cumulative_sum[i] = cumulative_sum[i-1]+1
    else:
        cumulative_sum[i] = cumulative_sum[i-1]



for l,r in zip(lll,rrr):
    
    print(cumulative_sum[r]-cumulative_sum[l-1])

Solution (Python):
q = int(input())
def prime(n):
    if any(n%i==0 or ((n+1)/2)%i==0 for i in range(2,int(n**(1/2))+1)):
        return False
    else:
        return True
cum = [0]*(10**5)
cum[3]=1
for i in range(4,10**5):
    cum[i]=cum[i-1]
    if prime(i):
        cum[i]+=1
for i in range(q):
    l,r = map(int,input().split())
    print(cum[r]-cum[l-1])

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

MAX = 100010
ps = [True] * MAX
ps[0] = ps[1] = False

def prime():
    for i in range(2, MAX):
        if ps[i]:
            j = 2 * i
            while j < MAX:
                ps[j] = False
                j += i

cs = [0] * MAX
def cnt():
    for i in range(1, MAX):
        if i % 2 == 1 and ps[i] and ps[(i + 1) // 2]:
            cs[i] = cs[i - 1] + 1
        else:
            cs[i] = cs[i - 1]

prime()
cnt()

Q = int(input())

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

Solution (Python):







def prime_set(limit=10**5):
    ret = [2]
    for x in range(3, limit+1, 2):
        is_prime = True
        sqrtx = int(pow(x, 0.5))

        for p in ret:
            if p > sqrtx:
                break

            if x % p == 0:
                is_prime = False
                break

        if is_prime:
            ret.append(x)

    return ret


def bin_search(xs, start, end, x):
    idx = start + (end-start) // 2
    if x < xs[idx]:
        return bin_search(xs, start, idx, x)
    elif x > xs[idx]:
        return bin_search(xs, idx+1, end, x)
    else:
        return idx


def geq_search(xs, start, end, x):
    if end - start < 2:
        if x <= xs[start]:
            return start
        else:
            return start+1

    idx = start + (end-start) // 2

    if x <= xs[start]:
        return start
    elif xs[idx-1] < x <= xs[idx]:
        return idx

    if x < xs[idx]:
        return geq_search(xs, start, idx+1, x)
    elif x > xs[idx]:
        return geq_search(xs, idx, end, x)
    else:
        return idx


def leq_search(xs, start, end, x):
    if end - start < 2:
        if x >= xs[start+1]:
            return start+1
        else:
            return start

    idx = start + (end-start) // 2

    if x >= xs[end-1]:
        return end-1
    elif xs[idx-1] <= x < xs[idx]:
        return idx-1

    if x < xs[idx]:
        return leq_search(xs, start, idx+1, x)
    elif x > xs[idx]:
        return leq_search(xs, idx, end, x)
    else:
        return idx


def main():
    
    
    
    
    
    
    
    

    primes = prime_set()
    primes_set = set(primes)
    len_primes = len(primes)

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

    
    likes = []
    for x in primes[1:]:
        if (x+1) // 2 in primes_set:
            likes.append(x)
    n_likes = len(likes)
    

    for i in range(Q):
        left_idx = geq_search(likes, 0, n_likes, l[i])
        right_idx = leq_search(likes, 0, n_likes, r[i])

        output = right_idx - left_idx + 1 if right_idx >= left_idx else 0
        print(output)

    
    

    
    
    
    

    
    
    
    

    

    
    

    
    
    

    
    


main()

Solution (Python):
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 is_prime

max = 100001
prime = primes(max)
a = [0]*max
for i in range(max):
    if i % 2 == 0:
        continue
    if prime[i] and prime[(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())
    print(s[r+1]-s[l])

Solution (Python):
U = 10**5
is_prime = [1]*(U+1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U+1, p):
            is_prime[q] = 0

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


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


q = int(input())
for _ in range(q):
    L, R = map(int, input().split())
    ans = S[R]-S[L-1]
    print(ans)

Solution (Python):
U = 10**5
is_prime = [1]*(U+1)
is_prime[0] = 0
is_prime[1] = 0
for p in range(2, int(U**.5)+1):
    if is_prime[p]:
        for q in range(2*p, U+1, p):
            is_prime[q] = 0

primes = [p for p, tf in enumerate(is_prime) if tf]


A = [0]*(10**5+1)
for prime in primes:
    if is_prime[(prime+1)//2]:
        A[prime] = 1


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


q = int(input())
for _ in range(q):
    L, R = map(int, input().split())
    ans = S[R]-S[L-1]
    print(ans)

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


def is_prime(x):
    if x == 1:
        return False
    d = 2
    while d**2 <= x:
        if x % d == 0:
            return False
        d += 1
    else:
        return True

primes = []
for x in range(2, 10**5+1):
    if is_prime(x):
        primes.append(x)
        
A = [0]*(10**5+1)
for prime in primes:
    if is_prime((prime+1)//2):
        A[prime] = 1


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


ans = []
for _ in range(q):
    L, R = map(int, input().split())
    cnt = S[R]-S[L-1]
    ans.append(cnt)

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

Solution (Python):

def sieve(n):
	s = [True] * n
	s[0] = s[1] = False
	for x in range(2, int(n ** 0.5) + 1):
		if s[x]:
			for i in range(2 * x, n, x):
				s[i] = False
	return s

is_prime = sieve(10 ** 5 + 1)
is_like2017 = [False] * (10 ** 5 + 1)
for i in range(10**5 + 1):
	if is_prime[i] and is_prime[(i + 1) // 2]:
		is_like2017[i] = True



c = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
	if is_like2017[i]:
		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 itertools
n = int(input())
lr = [[int(i) for i in input().split()] for _ in range(n)]
max = 101010
p = [1]*max
p[0] = 0
p[1] = 0
for i in range(2, max):
    if p[i] == 1:
        for j in range(int(i*2), max, i):
            p[j] = 0
a = [0]*(max+1)
for i in range(1, max, 2):
    if p[i] == p[(i+1)//2] == 1:
        a[i+1] = 1
a = list(itertools.accumulate(a))
for l, r in lr:
    print(a[r+1] - a[l])

Solution (Python):
import sys
import numpy as np
from itertools import accumulate


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


sys.setrecursionlimit(10 ** 9)


def main():
    def make_prime(U):
        is_prime = np.zeros(U, np.bool)
        is_prime[2] = 1
        is_prime[3::2] = 1
        M = int(U ** 0.5) + 1
        for p in range(3, M, 2):
            if is_prime[p]:
                is_prime[p * p :: p + p] = 0
        return is_prime

    primes = make_prime(10 ** 5 + 1)
    check = np.where(primes == True, 1, 0)
    for i in range(1, 10 ** 5 + 1):
        if i % 2 == 1:
            if primes[i]:
                if not primes[(i + 1) // 2]:
                    check[i] = 0
        else:
            continue
    check[2] = 0
    check = list(accumulate(check))
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(check[r] - check[l - 1])


if __name__ == "__main__":
    main()

Solution (Python):
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

q = int(input())
list_Q = [ list(map(int,input().split(" "))) for i in range(q)]

num = pow(10, 5)
list_PRE = [0]*(2*num+10)
list_PRE[2] = 1
for i in range(1, 2*num+10, 2):
    if len(prime_factorize(i)) == 1:
        list_PRE[i] = 1

list_2017 = [0]*(2*num+10)
for i in range(1, num+1, 2):
    if list_PRE[i] == 1 and list_PRE[(i+1)//2] == 1:
        list_2017[i] = 1

list_ANS = []
cnt = 0
for i in list_2017:
    if i == 1:
        cnt += 1
        list_ANS.append(cnt)
    else:
        list_ANS.append(cnt)

for i, j in list_Q:
    print(list_ANS[j]-list_ANS[i-1])