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.
import math
import bisect
import heapq
from collections import deque

q = int(input())


def is_prime(n):
    prime = True

    for i in range(2, int(math.sqrt(n)) + 1):

        if n % i == 0:
            prime = False

    return prime


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

    for j in range(l, r + 1, 2):
        if is_prime(j) and is_prime(j * (j - 1) / 2):
            count += 1

    print(count)

import math
import bisect
import heapq
from collections import deque

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

    return l

p = prime_list(10**5)

like = [0 for _ in range(10**5 + 1)]
for i in range(3,10**5+1,2):
    if p[i] and p[(i+1)//2]:
        like[i] = 1

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

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