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

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

Solution (Python):
def primes(n):
    primes = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            primes.append(i)
    return is_prime


Q = int(input())

ps = primes(100000)
like_numbers = [False] * 100001
for i in range(3, 100001, 2):
    if ps[i] and ps[(i + 1) // 2]:
        like_numbers[i] = True

like_numbers_cnt = [0] * 100001

for i in range(1, 100001):
    if like_numbers[i]:
        like_numbers_cnt[i] = like_numbers_cnt[i - 1] + 1
    else:
        like_numbers_cnt[i] = like_numbers_cnt[i - 1]

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

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

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

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

like = []
sieve1 = sieve(10**5)[1]
is_prime = sieve(10**5)[0]

for i in sieve1[1:]:
    if is_prime[(i+1) // 2-1]:
        like.append(i)

li = [0] * (10**5 + 10)

for i in like:
    li[i] = 1

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

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

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    
    Q = Scanner.int()
    L = [0] * Q
    R = [0] * Q
    for i in range(Q):
        L[i], R[i] = Scanner.map_int()
    MAX = int(1e05) + 10
    sums = [0] * MAX
    for n in range(MAX - 1):
        sums[n+1] = sums[n]
        if n % 2 == 1 and Math.isPrime(n) and Math.isPrime((n + 1) // 2):
            sums[n+1] += 1
    for i in range(Q):
        print(sums[R[i] + 1] - sums[L[i]])
    return


if __name__ == "__main__":
    main()

Solution (Python):
import math

Q = int(input())
lr =  [list(map(int, input().split())) for _ in range(Q)]

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

sosu_list = primes(10**5+7)

like2017 = [0] * (10**5+7)
for i in range(len(sosu_list)-1):
    if i % 2 == 1 and sosu_list[i]:
        if sosu_list[(i+1)//2]:
            like2017[i] = like2017[i-1] + 1
            continue
    like2017[i] = like2017[i-1]

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

Solution (Python):
MAX= 101010
is_prime = [ 1 ] * MAX
is_prime[0] = is_prime[1] = 0
for i in range( MAX ):
    if is_prime[ i ] == 0:
        continue
    for j in range( 2 * i, MAX, i ):
        is_prime[ j ] = 0

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

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

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

Solution (Python):
import math
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
n= 10**5

is_prime=[True]*(n+1)
is_prime[0]=is_prime[1]=False
for i in range(2,int(math.sqrt(n))+1):
	if is_prime[i]:
		for j in range(2*i,n+1,i):
			is_prime[j]=False
L=[0,0]
c=0
for i in range(2,n+1):
	if is_prime[i] and is_prime[(i+1)//2]:
		c += 1
	L.append(c)
for l,r in lr:
	print(L[r]-L[l-1])

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

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)

from bisect import bisect_left,bisect_right
import numpy as np

ls=[]
rs=[]
for i in range(Q):
    l,r=map(int, input().split())
    ls.append(l)
    rs.append(r)
lmin=min(ls)
rmax=max(rs)
bool_prime=np.zeros(rmax+1,dtype=np.int64)
bool_2007=np.zeros(rmax+1,dtype=np.int64)

for p in primes:
    if p>rmax:
        break
    bool_prime[p]=1
    if p!=2 and bool_prime[(p+1)//2]==1:
        bool_2007[p]=1

cum2007=np.cumsum(bool_2007)
for i in range(Q):
    print(cum2007[rs[i]]-cum2007[ls[i]-1])

Solution (Python):
import numpy as np
U = 10**5+10
T = np.zeros(U, np.bool)
T[1] = 1
T[2] = 1
T[3::2] = 1
for i in range(3,U,2):
  if i*i>U:
    break
  if T[i]:
    T[i*i::i+i] = 0
A = np.zeros(U, np.bool)
for i in range(3,U,2):
  if T[i]==1 and T[(i+1)//2]==1:
     A[i] = 1
A[1] = 0
A[2] = 0
A = A.cumsum()
    
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  print(A[r]-A[l-1])

Solution (Python):
import sys
import bisect

input = sys.stdin.readline


def get_primes(n):
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i:: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    Q = int(input())
    lr = [[int(x) for x in input().split()] for _ in range(Q)]

    P = get_primes(10 ** 5 + 1)
    setP = set(P)
    like = []
    for p in P:
        if (p + 1) // 2 in setP:
            like.append(p)


    for l, r in lr:
        li = bisect.bisect_left(like, l)
        ri = bisect.bisect_right(like, r)
        print(ri - li)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect
from functools import lru_cache

input = sys.stdin.readline


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


def main():
    Q = int(input())
    lr = [[int(x) for x in input().split()] for _ in range(Q)]

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

    for l, r in lr:
        li = bisect.bisect_left(sosu, l)
        ri = bisect.bisect_right(sosu, r)
        print(ri - li)









if __name__ == '__main__':
    main()

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

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

for i in range(2,int(int(10**5)**0.5+1)):
    if PN[i]==1:
        cnt=2
        while i*cnt<10**5+1:
            PN[i*cnt]=0
            cnt+=1

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

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

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

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

Solution (Python):
import sys
input=sys.stdin.readline
N=100000
primes = set(range(3, N+1, 2))
for i in range(3, int(N**0.5+1)):
  primes.difference_update(range(i*3, N+1, i*2))
primes=set(primes)
primes.add(2)
FG=[0]*(N+1)
for i in range(1,N+1,2):
  FG[i-1]=FG[i-2]
  if i in primes and (i+1)//2 in primes:
    FG[i]=FG[i-1]+1
  else:
    FG[i]=FG[i-1]
for q in range(int(input())):
  l,r=map(int,input().split())
  print(FG[r]-FG[l-1])

Solution (Python):
import bisect
prime_check=[True for i in range(100000)]
prime_check[0]=False
prime_check[1]=False

prime_num=[]

for i in range(2,100000):
    if(prime_check[i]):
        prime_num.append(i)
        for j in range(2*i,100000,i):
            prime_check[j]=False

like_num=[]
for pi in prime_num:
    if(prime_check[(pi+1)//2]):
        like_num.append(pi)

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

Solution (Python):
n = 100000
plist = range(2,n+1)
for i in range(n):
    if plist[i]**2>n:
        break
    plist = [num for num in plist if num % plist[i] != 0 or num == plist[i]]
ok = [0]*n
for p in plist:
    ok[p] += 1
    if p*2-1 < n:
        ok[p*2-1] += 1
li = []
cnt = 0
for i in range(n):
    if ok[i] == 2:
        cnt += 1
    li.append(cnt)
Q = int(input())
qlist = []
for i in range(Q):
    l, r = map(int, input().split())
    qlist.append((l,r))
for x in qlist:
    (l, r) = x
    print(li[r]-li[l-1])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

Q = INT()
L = [LIST() for _ in range(Q)]

def prime_for(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 is_prime

prime = prime_for(10**5)

acc = [0]*10**5
for i in range(1, 10**5):
	if i%2 == 0:
		acc[i] = acc[i-1]
	if prime[i] and prime[int((i+1)/2)]:
		acc[i] = acc[i-1]+1
	else:
		acc[i] = acc[i-1]

for i in range(len(L)):
	print(acc[L[i][1]] - acc[L[i][0]-1])

Solution (Python):
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
n = 10 ** 5

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

L = [0, 0]
c = 0
for i in range(2, n + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        c += 1
    L.append(c)

ans = 0

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

Solution (Python):
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')


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

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

    return True


def main():
    Q = INT()
    LR = []

    lmin = INF
    rmax = 0
    for i in range(Q):
        l, r = MAP()
        lmin = l if l < lmin else lmin
        rmax = r if r > rmax else rmax
        LR.append([l, r])

    L = [0] * ((rmax - lmin)//2 + 2)
    for i, n in enumerate(range(lmin, rmax+2, 2)):
        L[i+1] = L[i] + (is_prime(n) and is_prime((n+1)//2))

    for q in range(Q):
        print(L[(LR[q][1] - lmin)//2+1] - L[(LR[q][0] - lmin)//2])


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
check = [2]
ans = [0,0]
count = 0
for i in range(3,10**5+1):
    if i % 2 == 0:
        ans.append(count)
    else:
        a = True
        for j in check:
            if j > i**0.5+1:
                break
            if i % j == 0:
                a = False
                break
        if a:
            check.append(i)
            
            if (i+1)//2 in check:  
                count += 1
        ans.append(count)

for i,j in l:
    print(ans[j-1]-ans[max(0,i-2)])

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

import math
def erato(n):
    prime=[]
    cnt=[0]*n
    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=erato(M)
cnt=[0]*M
for i in range(len(prime)):
  cnt[prime[i]]+=0.6
  if 2*prime[i]-1<M:
    cnt[2*prime[i]-1]+=0.6
 
for i in range(1,M):
  if cnt[i]>1:
    cnt[i]=cnt[i-1]//1+1
  else:
    cnt[i]=cnt[i-1]//1
    

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

Solution (Python):
import sys
stdin=sys.stdin
nl_i=lambda: list(map(int, stdin.readline().split()))

def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])


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

Solution (Python):
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

import sys
stdin=sys.stdin
temp=lambda: list(map(int, stdin.readline().split()))

for i in range(q):

 l,r=temp()
 print(b[r+1]-b[l])

Solution (Python):
def eratosthenes(n):
 is_p=[1]*n


 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:

   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p

lim=10**5+1

is_p=eratosthenes(lim)

q=int(input())

'''
b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])
'''
a = [0] * (10**5+2)
for i in range(3, 10**5+1, 2):
    if is_p[i] and is_p[(i+1)//2]:
        a[i] = 1
for i in range(1, 10**5+1):
    a[i+1] += a[i]

for i in range(q):
 l,r=map(int,input().split())

 print(a[r]-a[l-1])

Solution (Python):
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

'''
b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])
'''
a = [0] * (10**5+2)
for i in range(3, 10**5+1, 2):
    if is_p[i] and is_p[(i+1)//2]:
        a[i] = 1
for i in range(1, 10**5+1):
    a[i+1] += a[i]

for i in range(q):
 l,r=map(int,input().split())

 print(a[r]-a[l-1])

Solution (Python):
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0

 return is_p, p_list

lim=10**5+1
is_p, p_list=eratosthenes(lim)

q=int(input())

b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])

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

Solution (Python):
def eratosthenes(n):
 is_p=[1]*n
 p_list=[]

 is_p[0]=0
 is_p[1]=0

 for i in range(2,n):
  if is_p[i]:
   p_list.append(i)
   for j in range(i*i,n,i):
    is_p[j] = 0


 return is_p

q=int(input())

lim=10**5+1
is_p=eratosthenes(lim)



b=[0]
for i in range(1,lim+1):
 if is_p[i-1]==1 and is_p[i//2]==1:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])



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

Solution (Python):

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

q=int(input())
f=[1]*(10**5+1)
f[0],f[1]=0,0

for i in range(2,len(f)):
    if isPrime(i):
        for j in range(i*2,len(f),i):
            f[j]=0

c=[0]*(10**5+1)
for i in range(2,10**5+1):
    if i%2==1:
        if f[i]==1 and f[(i+1)//2]==1:
            c[i]=c[i-1]+1
            continue
        c[i]=c[i-1]
    else:
        c[i]=c[i-1]

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

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


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

c2017 = [0]
total = 0
for i in range(1, 10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        total += 1
    c2017.append(total)

for i in range(Q):
    l, r = LR[i]
    ans = (c2017[r] - c2017[l-1])
    print(ans)

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


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

n2017 = set()
c2017 = [0]
total = 0
for i in range(1, 10**5+1):
    if is_prime(i) and is_prime((i+1)//2):
        total += 1
    c2017.append(total)

for i in range(Q):
    l = L[i]
    r = R[i]
    ans = (c2017[r] - c2017[l-1])
    print(ans)

Solution (Python):
def factorization(n):
 p=2
 fcr=[]
 while p*p<=n:
  while n%p==0:
   fcr.append(p)
   n//=p
  p+=1
 if n>1:
  fcr.append(n)
 return fcr

q=int(input())

cnt=1
p_list=[1]
q_list=[0]
for i in range(3,10**5+1,2):
 a=factorization(i)
 b=factorization((i+1)//2)

 if len(a)==len(b)==1:
  cnt+=1
  q_list.append(1)
 else:
  q_list.append(0)

 p_list.append(cnt)

for i in range(q):
 l,r=map(int,input().split())

 c=p_list[r//2]-p_list[l//2]
 if q_list[l//2]==1:
  print(c+1)
 else:
  print(c)

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

	return is_prime

is_prime = Eratosthenes(limit)

fullfill = np.zeros(limit+1,np.int32)

for p in range(limit+1):
	if p*2+1 > limit:
		break
	elif is_prime[p] and is_prime[2*p-1]:
		fullfill[2*p-1] = 1

ans = np.cumsum(fullfill)

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

print(*A)

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

	return is_prime

is_prime = Eratosthenes(limit)

fullfill = np.zeros(limit+1,np.int32)

for p in range(limit+1):
	if p*2+1 > limit:
		break
	elif is_prime[p] and is_prime[2*p-1]:
		fullfill[2*p-1] = 1

ans = np.add.accumulate(fullfill)

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

print(*A)

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

def main():
    N = int(input())
    M = 100000
    def sieve(n):
        is_prime = [True for _ in range(n+1)]
        is_prime[0] = False

        for i in range(2, n+1):
            if is_prime[i-1]:
                j = 2 * i
                while j <= n:
                    is_prime[j-1] = False
                    j += i
        return is_prime
    prime = sieve(M)
    alike = [0]
    for i in range(1,M+1,2):
        if (prime[i-1] and prime[(i+1)//2-1]):
            alike.append(alike[-1]+1)
        else:
            alike.append(alike[-1])
            
    for i in range(N):
        l,r = map(int,input().split())
        l = (l+1)//2
        r = (r+1)//2
        print(alike[r]-alike[l-1])
    
    
if __name__ == "__main__":
    main()

Solution (Python):
q = int(input())
ll = []
rr = []
for i in range(q):
    l,r = map(int,input().split())
    ll.append(l)
    rr.append(r)

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

m = max(rr)
j = f(m)
cnt = [0]*(m+1)
for i in range(1,m+1):
    cnt[i] = cnt[i-1]
    if i%2 != 0 and j[i] and j[(i+1)//2]:
        cnt[i] += 1

for i in range(q):
    print(cnt[rr[i]]-cnt[ll[i]-1])

Solution (Python):
q = int(input())
ll = []
rr = []
for i in range(q):
    l,r = map(int,input().split())
    ll.append(l)
    rr.append(r)

m = min(ll)
M = max(rr)
cnt = [0]*(M+2)

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

s = 0
for i in range(m,M+1,2):
    if is_prime(i) and is_prime((i+1)//2):
        s += 1
    cnt[i] = s

for i in range(q):
    print(cnt[rr[i]]-cnt[ll[i]-2])

Solution (Python):
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def main():
    MAX = 10 ** 5
    Q = int(input())

    ans = np.array([0] * (MAX + 1))
    sum = 0
    prime = set()
    memo = np.array([False] * 2 + [True] * (MAX - 1))
    for i in range(2, MAX + 1):
        if memo[i]:
            prime.add(i)
            for j in range(i * 2, MAX + 1, i):
                memo[j] = False
            if (i + 1) // 2 in prime:
                sum += 1
        ans[i] = sum
    
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ans[r] - ans[l-1])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    MAX = 10 ** 5
    Q = int(input())

    ans = [0] * (MAX + 1)
    sum = 0
    prime = set()
    memo = [False] * 2 + [True] * (MAX - 1)
    for i in range(2, MAX + 1):
        if memo[i]:
            prime.add(i)
            for j in range(i * 2, MAX + 1, i):
                memo[j] = False
            if (i + 1) // 2 in prime:
                sum += 1
        ans[i] = sum
    
    for _ in range(Q):
        l, r = map(int, input().split())
        print(ans[r] - ans[l-1])

if __name__ == '__main__':
    main()

Solution (Python):

MAX = int(10e5)
is_prime = [True] * MAX
is_prime[0], is_prime[1] = False, False
for i in range(2, MAX):
    if not is_prime[i]:
        continue
    for j in range(i * 2, MAX, i):
        is_prime[j] = False


a = [0] * MAX
for i in range(MAX):
    if i % 2 == 0:
        continue
    if is_prime[i] and is_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 = [int(i) for i in input().split()]
    print(s[r + 1] - s[l])

Solution (Python):
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
N = 10**5
c = [0] * (N+1)
tf = [False] * (N+1)

for i in range(2, N+1):
    if not tf[i]:
        for j in range(i*2, N+1, i):
            tf[j] = True
for i in range(3, N, 2):
    if not tf[i] and not tf[(i+1)//2]:
        c[i] += 1

for i in range(3, N, 1):
    c[i] += c[i-1]
for l, r in lr:
    print(c[r] - c[l-1])

Solution (Python):
import itertools
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)





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

M = 10 ** 5 + 1
is_prime = np.ones(M, np.bool)
is_prime2 = np.ones(M, np.bool)
is_prime[1] = 0

for i in range(2, M):
    if i*i > M:
        break

    if is_prime[i]:
        is_prime[i+i::i] = 0

for i in range(3, M, 2):
    n = (i+1)//2
    is_prime2[i] = is_prime[n]

is_near_2017 = np.ones(M, np.bool)
is_near_2017[2::2] = 0
is_near_2017[1] = 0

for i in range(3, M, 2):
    is_near_2017[i] = is_prime[i] & is_prime2[i]


cnt = np.cumsum(is_near_2017)

ans = []
for l, r in LR:
    a = cnt[r] - cnt[l-1]
    ans.append(str(a))

print("\n".join(ans))

Solution (Python):
N = 10**5
prime_list = [True] * (N+1)        
count_list = [0] * (N+1)
for i in range(2, N+1, 1):
    if prime_list[i]:
        for j in range(i+i, N+1, i):
            prime_list[j] = False

for i in range(3, N+1, 2):
    if prime_list[i] and prime_list[(i+1)//2]:
        count_list[i] += 1

for i in range(3, N+1, 1):
    count_list[i] += count_list[i-1]

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

Solution (Python):
N = 10**5
prime_list = [True] * (N+1)        
count_list = [0] * (N+1)
for i in range(2, N+1, 1):
    if prime_list[i]:
        for j in range(i+i, N+1, i):
            prime_list[j] = False

for i in range(3, N+1, 2):
    if prime_list[i] and prime_list[(i+1)//2]:
        count_list[i] += 1

for i in range(3, N+1, 1):
    count_list[i] += count_list[i-1]

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

Solution (Python):
import bisect

def Get_Sieve_of_Eratosthenes(N):
    prime_list = [2]
    limit = int(N ** 0.5)
    numeric_data = [i for i in range(3, N, 2)]
    while True:
        prime = numeric_data[0]
        if prime >= limit:
            return prime_list + numeric_data
        prime_list.append(prime)
        numeric_data = [x for x in numeric_data if x % prime != 0]

def Get_2017_like_number(N, prime_list):
    ans_list = []
    for p in prime_list:
        if (p+1)//2 in prime_list:
            ans_list.append(p)
    return ans_list


def main():
    N = 10 ** 5
    prime_list = Get_Sieve_of_Eratosthenes(N)
    like_number_list = Get_2017_like_number(N, prime_list)

    
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    
    for q in Query:
        l = q[0]
        r = q[1]
        print(bisect.bisect_right(like_number_list, r) - bisect.bisect_left(like_number_list, l))


if __name__ == "__main__":
    main()

Solution (Python):
import bisect

def Get_Sieve_of_Eratosthenes(N):
    prime_list = [2]
    limit = int(N ** 0.5)
    numeric_data = [i for i in range(3, N, 2)]
    while True:
        prime = numeric_data[0]
        if prime >= limit:
            return prime_list + numeric_data
        prime_list.append(prime)
        numeric_data = [x for x in numeric_data if x % prime != 0]

def Get_2017_like_number(N, prime_list):
    ans_list = []
    for p in prime_list:
        if (p+1)//2 in prime_list:
            ans_list.append(p)
    return ans_list


def main():
    N = 10 ** 5
    prime_list = Get_Sieve_of_Eratosthenes(N)
    like_number_list = Get_2017_like_number(N, prime_list)

    
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    
    for q in Query:
        l = q[0]
        r = q[1]
        print(bisect.bisect_right(like_number_list, r) - bisect.bisect_left(like_number_list, l))


if __name__ == "__main__":
    main()

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

Q = iin()
lr = [iln() for _ in range(Q)]
max_num = 10**5
def sieves_of_e(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

primes = sieves_of_e(max_num)

c = [0 for _ in range(max_num+2)]
for i in range(max_num+1):
    c[i+1] = c[i]
    if i % 2 == 1 and primes[i] and primes[(i+1)//2]: c[i+1] += 1

for i in range(Q):
    left = lr[i][0]
    right = lr[i][1]+1
    print(c[right]-c[left])