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



Sample input:
1
3 7


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def isPrime(i):
    if i == 2:
        return True
    p = 2
    tmp = i ** 0.5
    while i != 1:
        if i % p == 0:
            return False
        elif p > tmp:
            return True
        else:
            p += 1
    return True


class RSQ_segment_tree:
    """Range Sum Query
    0 indexed
    """

    def __init__(self, init_num, n):
        # represent tree as array
        # parent of k : (k - 1) // 2
        # children of k : 2 * k + 1 and 2 * k + 2
        self.ex = 0
        while(2 ** self.ex < n):
            self.ex += 1
        self.bottom = 2 ** self.ex - 1
        self.tree = [init_num for _ in range(2 ** (self.ex + 1) - 1)]

    def __str__(self):
        tmp = "tree structure\n"
        tree = str(self.tree)
        return tmp + tree + "\n"

    def min_update(self, position, new):
        # chi : child
        # par : parent
        chi = self.bottom + position
        self.tree[chi] = new
        for _ in range(self.ex):
            par = (chi - 1) // 2
            ano_chi = [chi + 1, chi - 1][chi % 2 == 0]
            self.tree[par] = min(self.tree[chi], self.tree[ano_chi])
            chi = par
        return True
    
    def sum_find(self, left, right, first=False):
        """[left, right]"""
        if first is True:    
            left = self.bottom + left
            right = self.bottom + right
        if left == right:
            return self.tree[left]

        if left % 2 == 1:
            tmpl = 0
        else:
            tmpl = -1 * self.tree[left-1]
            left -= 1

        if right % 2 == 1:
            tmpr = self.tree[right]
            right -= 1
        else:
            tmpr = 0
        # print(left, right)
        return tmpl + tmpr + self.sum_find((left-1)//2, (right-1)//2)
    
    def make_sum(self):
        for i in reversed(range(self.bottom)):
            self.tree[i] = self.tree[(i+1)*2] + self.tree[(i+1)*2-1]


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

Q = int(input())
query = [inpl() for i in range(Q)]
N = 10 ** 5

rsq = RSQ_segment_tree(0, N)
prime = [False] * (N+1)
for i in range(2, N+1):
    prime[i] = isPrime(i)
    rsq.tree[i+rsq.bottom] = int(prime[i] and prime[(i+1)//2])

rsq.make_sum()
# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for l, r in query:
    print(rsq.sum_find(l, r, first=True))