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):
PN = [i for i in range(100001)]
i = 2
while True:
    if i >= len(PN):
        break
    j = i * 2
    while True:
        if j >= len(PN):
            break
        PN[j] = 0
        j += i
    while True:
        i += 1
        if i >= len(PN):
            break
        if PN[i] != 0:
            break
PN[1] = 0
PN_2 = [0]
DPN = [0]
for i in range(1, 100001):
    if PN[i] != 0 and PN[int((PN[i] + 1) / 2)] != 0:
        PN_2.append(PN[i])
        DPN.append(DPN[i - 1] + 1)
    else:
        PN_2.append(0)
        DPN.append(DPN[i - 1])





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

Solution (Python):
import bisect
def mark(s, x):
    for i in xrange(x + x, len(s), x):
        s[i] = False

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


primes = sieve(10**5)
likes = []
for i in primes:
	if primes[bisect.bisect_left(primes,(i+1)/2)] == (i+1)/2:
		likes.append(i)

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

i = 1
j = 0

while i < 10**5+1 and j < len(likes):
	if likes[j] > i:
		cs[i] = cs[i-1]

	else:
		cs[i] = cs[i-1]+1
		j +=1
	i += 1
t = cs[i-1]
while i < 10**5+1:
	cs[i] = t
	i += 1

q = int(input())

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

Solution (Python):
import math
q = int(input())
x = []
for i in range(q):
    x1,y1=[int(i) for i in input().split()]
    x.append([x1,y1])
def so(k):
    n = True
    if k % 2 == 0 and k != 2:
      return False
    for divisor in range(2, math.floor(math.sqrt(k))+1):
      if k % divisor == 0:
        n = False           
    return n
map1 = [None for i in range(100005)]
map2 = [0 for i in range(100005)]
for i in range(2,100001):
  map1[i] = so(i)
for i in range(2,100001):
  if (map1[i] == True and map1[(i+1)//2] == True):
    map2[i] = map2[i-1] +1
  else:
    map2[i] = map2[i-1]
for a,b in x:
  print(map2[b]-map2[a-1])

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

n = 100000
P = [False] * n
P[2] = True
for i in range(3, n, 2):
    k = True
    for j in range(3, int(math.sqrt(i)) + 1, 2):
        if i % j == 0:
            k = False
            break
    if k:
        P[i] = True
 

a = [0] * n
for i in range(1, n, 2):
    j = (i + 1) // 2
    if P[i] and P[j]:
        a[i] = 1

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

Solution (Python):
from itertools import accumulate
def gen_prime(n):
    seq = list(range(2, n))
    while len(seq) > 0:
        prime = seq.pop(0)
        yield prime
        if n ** 0.5 >= prime:
            seq = [i for i in seq if not i % prime == 0]


N = 10 ** 5
primes = list(gen_prime(N + 1))
is_prime = [False] * (N + 1)
for i in primes:
    is_prime[i] = True

n_2017 = [is_prime[i] and is_prime[(i + 1) // 2] for i in range(0, N + 1)]
sum_n = list(accumulate(n_2017))

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p, t


@mt
def slv(Q, LR):
    N = 100000
    p, t = eratosthenes(N)
    qt = [0] * N
    for i in range(3, N):
        qt[i] = qt[i-1]
        if t[i] and t[(i+1)//2]:
            qt[i] += 1

    for l, r in LR:
        print(qt[r] - qt[l-1])


def main():
    Q = read_int()
    LR = [read_int_n() for _ in range(Q)]
    slv(Q, LR)


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = [1]
    t = [True] * n

    t[1] = True
    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p


@mt
def slv(Q, LR):
    N = 100000
    p = eratosthenes(N)
    qt = [0] * N
    for i in range(2, N):
        qt[i] = qt[i-1]
        if i % 2 == 0:
            continue

        q = (i+1)//2
        qi = bisect.bisect_left(p, q)
        ii = bisect.bisect_left(p, i)
        if qi != len(p) and p[qi] == q and ii != len(p) and p[ii] == i:
            qt[i] += 1

    for l, r in LR:
        print(qt[r] - qt[l-1])
    
    


def main():
    Q = read_int()
    LR = [read_int_n() for _ in range(Q)]
    
    slv(Q, LR)


if __name__ == '__main__':
    main()

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

maxp = 100100

allPrimes = [1]
like2017 = []
primes_list = [0 for _ in range(maxp+1)]
import bisect

def isPrimeNum(num):
    if num in allPrimes:
        return True
    else:
        return False

def initPrimes(ma):
    furui = {i:0 for i in range(2,ma+1)}

    primes_list[1] = 1

    for i in range(2,ma):
        if furui[i] == 0:
            
            if i > 2 and primes_list[(i+1)//2] == 1:
                like2017.append(i)

            primes_list[i] = 1

            for h in range(1,ma):
                index = i * h
                if index>ma:
                     break
                furui[index] = 1




initPrimes(maxp)

count = 0
for _ in range(N):
    l,r = [int(x) for x in input().split()]

    f = bisect.bisect_left(like2017,l)
    t = bisect.bisect_right(like2017,r)

    print(t-f)

Solution (Python):
from itertools import accumulate, count, islice, takewhile
 
def eratosthenes():
    d = {}
    for q in count(2):
        p = d.pop(q, None)
        if p:
            x = next(x for x in count(q + p, p) if x not in d)
            d[x] = p
        else:
            yield q
            d[q*q] = q

def likes():
    xs = set()
    for p in eratosthenes():
        if p in xs:
            yield p
        xs.add(2*p - 1)

likeset = set(takewhile(lambda n: n <= 100000, likes()))
onehot = (i in likeset for i in range(100001))
likecounts = list(accumulate(onehot))

q = int(input())
lrs = [[int(x) for x in input().split()] for _ in range(q)]

for l, r in lrs:
    print(likecounts[r+1] - likecounts[l-1])

Solution (Python):
tf = [True] * 100001
tf[0] = tf[1] = True
for i in range(2, 320):
  if tf[i]:
    for j in range(i ** 2, 100001, i):
      tf[j] = False

tf2 = [False] * 100001
for i in range(3, 100001):
  if tf[i] and tf[(i + 1) // 2]:
    tf2[i] = True

count = []
acc = 0
for i in range(100001):
  acc += tf2[i]
  count.append(acc)

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

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


def is_prime():
    a = [0 for i in range(MAX_N+1)]
    for i in range(2, MAX_N+1):
        for j in range(2*i, MAX_N+1, i):
            a[j] += 1

    for i in range(2, MAX_N+1):
        if a[i] == 0:
            p_lst[i] = 1


def main():
    q = int(input())

    is_prime()
    s, idx = [0 for i in range(MAX_N+1)], 0
    for i in range(2, MAX_N+1):
        if p_lst[i] == 1 and p_lst[(i+1)//2] == 1:
            s[i] = s[i-1] + 1
        else:
            s[i] = s[i-1]

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


if __name__ == '__main__':
    main()

Solution (Python):
import math as m

def judge_prime(num):
    isPrime = [True]*(num+1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i*2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
        
    
    like2017_list = []
    for prime in range(3,num+1,2):


        if isPrime[int(prime)] and isPrime[int((prime+1)/2)]:
            like2017_list.append(prime)
        
    return like2017_list
        
    
    
def main():
    












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

    
    MAX_Q = 10**5
    
    like2017_list = judge_prime(MAX_Q)

    
    
    csum = [0]*(MAX_Q+1)
    i = 0
    cnt = 0
    for like2017 in like2017_list:
        while i < like2017:
            csum[i] = cnt
            i += 1
        cnt += 1
    for i in range(like2017_list[-1], MAX_Q+1):
        csum[i] = cnt
        
    
    for i in range(Q):
        print(csum[LR[i][1]] - csum[LR[i][0]-1])


    
if __name__ == "__main__":
    main()

Solution (Python):
def prime(n):
	prime = [2,3,5]
	for i in range(6,n+1):
		check = True
		for k in range(2,int(i**0.5)+1):
			if i%k == 0:
				check = False
				break
		if check:
			prime.append(i)
	return prime

prime = prime(100000)
data = dict()
for i in range(1,100001):
	data[i] = 0
for k in range(len(prime)):
	data[prime[k]] = 1

anotherdata = dict()
for i in range(0,100001):
	anotherdata[i] = 0
counter = 1
for k in range(1,len(prime)):
	if data[(prime[k]+1)/2] == 1:
		anotherdata[prime[k]] = counter
		counter += 1
anotherdata[1] = 0
anotherdata[2] = 0
for e in range(3,100001):
	if anotherdata[e] == 0:
		anotherdata[e] = anotherdata[e-1]

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

Solution (Python):
def get_prime_list(n):
    L = tuple(range(2,n+1))
    for i in range(2,int((n+1)**0.5)):
        if i not in L:
            continue
        L = tuple(j for j in L if j <= i) + tuple(j for j in L if j > i and j % i != 0)
    return L

Q = int(input())
lr = [tuple(map(int,input().split())) for _ in range(Q)]
prime_list = get_prime_list(100000)
like_num = tuple(i for i in prime_list if (i+1)//2 in prime_list)
L = [0] * 100002
for i in range(3,100001,2):
    if i in like_num:
        L[i] = L[i-2]+1
    else:
        L[i] = L[i-2]
for l,r in lr:
    print(L[r]-L[l-2])

Solution (Python):

"""
Created on Wed Jun 20 16:39:29 2018

@author: Yuya
"""

import numpy


N =list(range(3, 100001, 2))

for i in range(49999):
    flag = -1
    Len_N = len(N)
    for j in range(Len_N-1, i, -1):
        if N[j]%N[i] == 0:
            del N[j]
            flag = 1
    if flag < 0:
        break

N = [2]+N

for i in range(len(N)-1, 0, -1):
    if not (N[i]+1)//2 in N:
        del N[i]
    
N_2017 = N[1:]


Sum_N = [0]*100000

for i in range(len(N_2017)):
    Sum_N[N_2017[i-1]] = 1
    
res = list(numpy.cumsum(Sum_N))

Q = int(input())

L_Q = [0]*Q
R_Q = [0]*Q

for i in range(Q):
    L, R = map(int,input().split())
    L_Q[i] = L
    R_Q[i] = R

for i in range(Q):
    print(res[R_Q[i]]-res[L_Q[i]-1])

Solution (Python):
import math

Q = int(input())


n = 100000
P = [False] * n
P[2] = True
for i in range(3, n, 2):
    k = True
    for j in range(3, int(math.sqrt(i)) + 1, 2):
        if i % j == 0:
            k = False
            break
    if k:
        P[i] = True


a = [0] * n
for i in range(1, n, 2):
    j = (i + 1) // 2
    if P[i] and P[j]:
        a[i] = 1

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

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

Solution (Python):
class Prime:
    def __init__(self,number):
        self.jud=[True]*(number+5)
        self.pri=[]
        self.jud[0]=False
        self.jud[1]=False
        for i in range(number):
            if self.jud[i]:
                self.pri.append(i)
                for j in range(2,(number)//i+1):
                    self.jud[i*j]=False
    
    def judge(self,x):
        return self.jud[x]
    
    def decom(self,x):
        s=x
        a =[]
        if s==1:
            return a
        while s>1:
            for p in self.pri:
                if s%p==0:
                    a.append(p)
                    s=s//p
                    break
        return a
            

A=Prime(10**5)
Q=int(input())
Que=[[int(i) for i in input().split()] for i in range(Q)]
cou=[0]*(10**5+1)
for i in range(3,10**5+1):
    if A.judge(i) and A.judge((i+1)//2):
        cou[i]=cou[i-1]+1
    else:
        cou[i]=cou[i-1]
ans=[]
for l,r in Que:
    ans.append(cou[r]-cou[l-1])
print('\n'.join(map(str,ans)))

Solution (Python):
import math
Q=int(input())
querys = [list(map(int,input().split())) for x in range(Q)]
large = max(q[1] for q in querys)
like2017 = [0]*(large+1)


cands = [False if (5 < i and (i%2)*(i%3)*(i%5) == 0) or (i < 2) or (i == 4) else True for i in range(large+1)]
if 5 <= large:
  for i in range(6,int(math.sqrt(large)+1)):
    if cands[i]:
      for j in range(i*i,large+1,i):
        if cands[j]:
          cands[j] = False


for x in range(large+1):
  if cands[x] and cands[(x+1)//2]:
    like2017[x] = 1
for y in range(1,large+1):
  like2017[y] += like2017[y-1]

for q in querys:
  print(like2017[q[1]]-like2017[q[0]-1])

Solution (Python):
def main():
    Q = int(input())
    L = [0 for _ in range(Q)]
    R = [0 for _ in range(Q)]
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    N = 100000
    sosu = [1 for _ in range(N)]
    sosu[0] = 0
    for i in range(1,int(N**0.5)):
        k = i+1
        if sosu[i] == 1:
            j = k + k
            while j <= N:
                sosu[j-1] = 0
                j = j+k
    like = [0 for _ in range(N)]
    for i in range(2, N, 2):
        if sosu[i]==1 and sosu[(i+2)//2-1]==1:
            like[i] = 1
    like_wa = [0 for _ in range(N+1)]
    for i in range(N):
        like_wa[i+1] = like_wa[i] + like[i]

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

if __name__ == '__main__':
    main()

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

Q = int(input())
L = [0]
isPrime = makePrimeChecker(100000)
for i in range(1, 100000):
    if i&1==1 and isPrime[i] and isPrime[(i+1)//2]:
        L.append(L[-1] + 1)
    else:
        L.append(L[-1])
for i in range(Q):
    l, r = map(int, input().split())
    print(L[r] - L[l-1])

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

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


M = 10**5+10
prime=[True]*M
prime[0]=False
prime[1]=False
for i in range(2,M):
    if prime[i]:
        for j in range(2,(M-1)//i+1):
            prime[i*j]=False
con=[0]*M
for j in range(3,M):
    if prime[j] and prime[(j+1)//2]:
        con[j] = con[j-1]+1
    else:
        con[j]=con[j-1]


ans =[]
for i in range(Q):
    l,r = que[i]
    ans.append(con[r]-con[l-1])
print('\n'.join(map(str, ans)))

Solution (Python):
from math import sqrt
from itertools import accumulate

prime = [2]
more_prime = [0] * 100000
for i in range(3, 100000):
	j = 2
	while j <= sqrt(i):
		if i % j == 0:
			break
		j += 1
	else:
		prime.append(i)
		if (i + 1) // 2 in prime:
			more_prime[i-1] = 1

ans = list(accumulate(more_prime))

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

Solution (Python):
isPrime = [True for i in range(100001)]
isPrime[0] = False
isPrime[1] = False

for i in range(2, 100001):
    if isPrime[i]:
        j = 2
        while i*j <= 100000:
            isPrime[i*j] = False
            j += 1

isSimilar = [True for i in range(100001)]
for i in range(100001):
    if isPrime[i] and isPrime[(i+1)//2]:
        pass
    else:
        isSimilar[i] = False

cnt = [0 for i in range(1, 100010)]
for i in range(1, 100001):
    cnt[i] = cnt[i-1] + [0, 1][isSimilar[i]]

q = int(input())
lrs = list()
for i in range(q):
    lrs.append(list(map(int, input().split())))

for l, r in lrs:
    print(cnt[r]-cnt[l-1])

Solution (Python):
isPrime = [True for i in range(100010)]

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

isSimilar = [True for i in range(100010)]
for i in range(100010):
    if isPrime[i] and isPrime[(i+1)//2]:
        isSimilar[i]=True
    else:
        isSimilar[i]=False

cnt = [0 for i in range(100010)]
for i in range(1, 100010):
    cnt[i] = cnt[i-1] + [0, 1][isSimilar[i]]

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

Solution (Python):
q = int(input())
l = list(range(2, 10**5+1))
prime = [1]*(10**5+1)
prime[0], prime[1] = 0, 0
temp = [0]*(10**5+1)
counts = [0]*(10**5+1)
ans = 0
for i in range(2, int((10**5)**0.5) + 1):
  if not prime[i]:
    continue

  for j in range(i*2, int(10**5) + 1, i):
    prime[j] = 0

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

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

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

Solution (Python):
def eratosthenesAray(N):
    prime=[True]*(N+1)
    prime[0]=False
    prime[1]=False
    for i in range(2,N+1):
        if prime[i]:
            for j in range(i+i,N+1,i):
                prime[j]=False
    return prime

N=int(input().strip())
primes=eratosthenesAray(100000)
ruiseki=[0]*100001
for i in range(1,100001):
    ruiseki[i]=ruiseki[i-1]
    if primes[i] and primes[(i+1)//2]:
        ruiseki[i]+=1
for i in range(N):
    l,r=map(int,input().split())
    print(ruiseki[r]-ruiseki[l-1])

Solution (Python):
List = [True for x in range(100001)]
c = [0 for x in range(100001)]

List[0] = False
List[1] = False
List[2] = True
for i in range(2,100001):
    if(List[i] == True):
        for j in range(i+i,100001,i):
            List[j] = False

for i in range(3,100001, 2):
    if(List[i] and List[int((i+1)/2)]):
        
        c[i] += 1

for i in range(100001):
    c[i] += c[i-1]

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

Solution (Python):
p = [True for _ in range(10**5)]
p[0] = False
p[1] = False
for i in range(4,10**5,2):
    p[i] = False
for i in range(3,10**5,2):
    if p[i]:
        d = 2
        while i*d < 10**5:
            p[i*d] = False
            d += 1
n = [0 for _ in range(10**5)]
for i in range(1,10**5,2):
    n[i] = n[i-2]
    if p[i] and p[(i+1)/2]:
        n[i] = n[i-2] + 1

q = int(raw_input())
for _ in range(q):
    l,r = map(int, raw_input().split())
    k = n[r] - n[l]
    if l > 1 and n[l] > n[l-2]:
        k += 1
    print k

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

Solution (Python):
import numpy as np

q = int(input())

params = [[int(el) for el in input().split()] for _ in range(q)]


def get_nearst(max):
    primes = [True for i in range(max+1)]

    for i in range(2, max):
        if primes[i]:
            for j in range(i+i, max+1, i):
                primes[j] = False

    primes[0] = False
    primes[1] = False

    neast = [False for i in range(max)]

    for i in range(3, max+1, 2):
        if primes[i] and primes[int((i+1)/2)]:
            neast[i] = True

    return tuple(neast)


primes = get_nearst(max=10**5)

ruise = np.cumsum(primes)




for l, r in params:
    if r == l:
        print(int(primes[r]))
    else:
        print(ruise[r]-ruise[l-1])

Solution (Python):
q=int(input())
lr=[list(map(int, input().split())) for i in range(q)]
l,r=[],[]
for a in lr:
    l.append(a[0])
    r.append(a[1])
mr=max(r)
x = [True]*(mr+1)
x[0]=False
x[1]=False

for i in range(mr+1):
    if x[i]:
        for j in range(2*i, mr+1, i):
            x[j] = False
c=[0]*(mr+1)
for i in range(1,mr+1):
    if x[i] and x[(i+1)//2]:
        c[i] = c[i-1]+1
    else:
        c[i] = c[i-1]
for i in range(q):
    print(c[r[i]]-c[l[i]-1])

Solution (Python):
work = [True] * 100001
work[0] = False
work[1] = False
primes = []
for i in range(100001):
    if work[i]:
        for j in range(2* i, 100001, i):
            work[j] = False


csum = [0] * 100001
index = 0
for i in range(1, 100001):
    if work[i] and work[(i+1)//2]:
        csum[i] = csum[i - 1] + 1
    else:
        csum[i] = csum[i - 1]

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

Solution (Python):
from collections import Counter
P = [0] * 100001
Q = [0] * 100002
P[0] = 1
P[1] = 1

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

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

for k in range(3, 100000, 2):
    if P[k] == 0 and P[(k + 1) // 2] == 0:
        Q[k] = 1
for l in range(100000):
    Q[l+1] += Q[l]

for m in range(n):
    l, r = num[m][0], num[m][1]
    print(Q[r] - Q[l-1])

Solution (Python):
N = 100001
A,B = [True]*N,[0]*N
A[0],A[1] = False,False
for i in range(2,N):
    if A[i]:
        for j in range(i*2,N,i):
            A[j] = False
c=0
for i in range(3,N):
    if A[i] and A[(i+1)//2]:
        c += 1
    B[i] = c
Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    print(B[r]-B[l-1])

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

MAX = 10**5
is_primes = [True for _ in range(MAX+1)]
is_primes[0] = False
is_primes[1] = False

for i in range(2, MAX):
    if is_primes[i]:
        for j in range(2*i, MAX, i):
            is_primes[j] = False

count = 0
count_2017 = [0, 0]
for i in range(3, MAX, 2):
    if is_primes[i]:
        if is_primes[(i+1)//2]:
            count += 1
    count_2017.append(count)

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

Solution (Python):
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

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

A[0] = A[1] = False


B=[0]*100002

for i in range(100000):
    if A[i] and (i+1)%2 == 0:
        if A[int((i+1)/2)]:
            B[i] = B[i-1]+1
        else:
            B[i] = B[i-1]          
    else:
        B[i] = B[i-1]
        
q = int(input())

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

Solution (Python):
q = int(input())
a = [[int(i) for i in input().split()] for i in range(q)]
prime = [True]*100000
prime[0],prime[1] = False,False
for i in range(2, 317):
	if not prime[i]: continue
	for j in range(i*2,100000,i): prime[j] = False
y = [0]
for i in range(3,10**5,2):
	if prime[i] and prime[(i+1)//2]: y.append(y[-1]+1)
	else: y.append(y[-1])
for i in a:
	print(y[(i[1]-1)//2]-y[max((i[0]-3)//2,0)])

Solution (Python):
import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
R=[0 for i in range(M+1)]
k=0
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
            k+=1
    R[i]=k
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])

Solution (Python):
import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
R=[0 for i in range(M+1)]
k=0
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
            k+=1
    R[i]=k
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])

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

max_l = max(lr, key=lambda x:x[1])[1]

prime = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = filter(lambda x: x%prime[m-1] != 0,prime[m:])
    prime = prime[:m]
    prime.extend(b)
    m += 1
    if m > len(prime):
        break

like2017 = {-1:0,1:0}
for i in range(3,max_l+2,2):
    k = 0
    for j in prime:
        if (i%j == 0 or ((i+1)/2)%j == 0) and i != j and (i+1)/2 != j:
            k += 1
            break
    if k == 0:
        like2017[i] = like2017[i-2] + 1
    else:
        like2017[i] = like2017[i-2]


for i in range(Q):
    print(like2017[lr[i][1]]-like2017[lr[i][0]-2])

Solution (Python):
import math
def is_prime(x):
    if x < 2: return False  
    if x == 2 or x == 3 or x == 5: return True  
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False  

    
    pri = 7
    step = 4
    while pri <= math.sqrt(x):
        if x % pri == 0: return False

        pri += step
        step = 6 - step

    return True

Q = int(input())

prime = [0] * 100002
prime[0] = 0
prime[1] = 0
prime[2] = 0
num = 3

while num < 100002:
    prime[num] = prime[num - 1]
    if is_prime(num) and is_prime((num + 1) // 2):
        prime[num] += 1
    num += 1
ans = []

for i in range(Q):
    a, b = map(int, input().split())
    ans.append(prime[b] - prime[a-1])

for i in range(Q):
    print(ans[i])

Solution (Python):
MAX=100001
array=[True for i in range(MAX)]
array[1]=False
similar=[True for i in range(MAX)]

for i in range(2, MAX):
	if array[i]:
		for j in range(2, int(MAX/i)+1):
			if(j*i < MAX):
				array[i*j]=False
c=[0 for i in range(MAX)]
count=0

for i in range(2, MAX):
	if array[i] and array[int((i+1)/2)]:
		count+=1

	c[i]=count

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

Solution (Python):
import math
Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def calc_sosus(max_num):
	IsPrimes = [True] * (max_num + 1)
	IsPrimes[0] = False
	IsPrimes[1] = False
	for min_i in range(2, int(math.sqrt(max_num)) + 1):
		if IsPrimes[min_i]:
			for num in range(min_i*min_i, max_num+1, min_i):
				IsPrimes[num] = False
	return IsPrimes

IsPrimes = calc_sosus(max_num)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (IsPrimes[i]) & (((i+1) % 2)==0) & (IsPrimes[(i+1)/2]): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

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

Solution (Python):
import math

Q = int(input())
li = []
M = 0
for index in range(Q):
	l, r = map(int, input().split())
	li.append((l, r))
	M = max([M, l, r])

primes = list(range(M+1))
primes[0] = 0
primes[1] = 0
cut_root = math.sqrt(M+1)
for prime in primes:
	if prime > cut_root:
		break
	if prime == 0:
		continue
	for non_prime in range(2 * prime, M, prime):
		primes[non_prime] = 0
similar_2017 = [0 for _ in range(M+1)]
similar_2017[3] = 1
for i in range(5, M+1, 4):
	if primes[i] != 0:
		if primes[(i+1)//2] != 0:
			similar_2017[i] = 1
similar_sum = [0 for _ in range(M+1)]
for i in range(1,M+1):
	if similar_2017[i] == 1:
		similar_sum[i] = similar_sum[i-1] + 1
	else:
		similar_sum[i] = similar_sum[i-1]

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

Solution (Python):



import sys

isprime = None

def sieve(n):
    global isprime

    if n < 2:
        isprime = [False] * (n + 1)
        return

    isprime = [True if i % 2 != 0 else False for i in range(n + 1)]
    isprime[0] = isprime[1] = False
    isprime[2] = True

    from math import sqrt, ceil

    for i in range(3, int(sqrt(n)) + 1):
        if isprime[i] == True:
            for j in range(i + i, n + 1, i):
                isprime[j] = False

def main():
    global isprime

    sieve(100000)

    _ = sys.stdin.readline()

    csums = [0] * 100001
    for i in range(3, 100001):
        csums[i] += csums[i - 1]
        if isprime[i] == True and isprime[(i + 1) // 2] == True:
            csums[i] += 1

    for l, r in (map(int, line.split()) for line in sys.stdin.readlines()):
        print(csums[r] - csums[l - 1])

if __name__ == '__main__':
    main()

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

p = [1]*(100000+1)
p[0]=0
p[1]=0
        

for j in range(2,int(100000**0.5+1)):
    if p[j] == 0:
        continue
    for i in range(2,100000+1):
        if i!=j and i%j == 0:
            p[i] = 0
for i in range(100000-1, 1,-2):
    if p[int((i+1)/2)] == 0:
        p[i] = 0
p[2] = 0
for i in range(2,100000):
    p[i+1] += p[i]  

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