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.
q = int(input())
like2017 = []

def is_prime(x):
    if x==2:
        return True
    elif x%2==0:
        return False

    for i in range(3, x, 2):
        if x!=i and x%i==0:
            return False
    return True

for i in range(3, 9974, 2):
    if is_prime(i) and is_prime(int((i+1)/2)):
        like2017.append(i)
# print(like2017)
for i in range(q):
    l, r = map(int, input().split())
    left = 0
    right = 0
    for j in like2017:
        if l==1:
            left = 0
        if j < l:
            left = like2017.index(j)
        elif j > r:
            right = like2017.index(j)-1
            break
    print(right-left)

import numpy as np

q = int(input())


is_prime = np.ones(100001, dtype=int)
is_prime[0]=0
is_prime[1]=0

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

like2017 = [1 if is_prime[i] and is_prime[(i+1)//2] else 0 for i in range(0,100001) ]

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