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.
#!/usr/bin/env python3
#ABC84 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7


def get_prime(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
        for j in range(i*2,n+1,i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

prime = get_prime(10**5)
ansprime = [float('inf')]*(10**5)
for i in range(1,10**5+1,2):
    if i not in prime:
        continue
    if (i+1)//2 not in prime:
        continue
    ansprime[i] = i
ansprime.sort()
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    li = bisect.bisect_left(ansprime,l)
    ri = bisect.bisect_right(ansprime,r)
    print(ri-li)

#!/usr/bin/env python3
#ABC84 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

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

ansprime = [float('inf')]*(10**5)
for i in range(1,10**5+1,2):
    if is_prime[i] and is_prime[(i+1)//2]:
        ansprime[i] = i
ansprime.sort()
q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    li = bisect.bisect_left(ansprime,l)
    ri = bisect.bisect_right(ansprime,r)
    print(ri-li)
