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: Accepted

Solution code:
Q = int(input())

n = 10**5

import math
def primes():
    sieve = [True] * (n + 1)
    for x in range(2, math.ceil(math.sqrt(n))):
        y = x * 2
        while y <= n:
            sieve[y] = False
            y += x
    return [i for (i, x) in enumerate(sieve[2:], 2) if x]

list_p = primes()
set_p = set(list_p)

tbl = [0] * (n + 1)
for p in list_p:
    tbl[p] = 1 if ((p + 1) // 2) in set_p else 0

import itertools
tbl = list(itertools.accumulate(tbl))

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

Submission status: Accepted

Solution code:
from math import ceil
Q = int(input())

primeList = [1] * (100001)
cumA = [0] * (100001)

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

for i in range(1,100000):
  cumA[i+1] = cumA[i]
  if i%2 == 0 and primeList[(i+2)//2] == 1:
    cumA[i+1] += primeList[i+1]

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