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

Solution (Python):
Q = int(input())
N = int(10e5)

queries = []

def get_all_prime_numbers(N):
    values = list(range(1, N + 1))
    flags = [1] * N
    flags[0] = 0  
    for i in range(N):
        if flags[i] == 0:
            continue

        prime = values[i]
        for mult in range(2, N // prime + 1):
            cand = mult * prime
            if flags[cand - 1] == 1:
                flags[cand - 1] = 0

    prime_numbers = []
    for i in range(N):
        if flags[i] == 1:
            prime_numbers.append(values[i])
    return prime_numbers

prime_numbers_list = set(get_all_prime_numbers(N))

accum_sum = [0]  
for i in range(N // 2):
    num = 2 * i + 1
    if num in prime_numbers_list and (num + 1) // 2 in prime_numbers_list:
        accum_sum.append(accum_sum[-1] + 1)
    else:
        accum_sum.append(accum_sum[-1])

for i in range(Q):
    l, r = list(map(int, input().split()))
    l_ind, r_ind = (l + 1) // 2, (r + 1) // 2
    print(accum_sum[r_ind] - accum_sum[l_ind - 1])

Solution (Python):
from collections import Counter
ma = 100000

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

q = int(input())
a = primes(100000)
b = []
for i in a:
    b.append(i*2 - 1)
    
aa = Counter(a)
bb = Counter(b)

rui = [0] * (ma+1)
for i in range(1,ma+1):
    if aa[i] == 1 and bb[i] == 1:
        rui[i] = rui[i-1] + 1
    else:
        rui[i] = rui[i-1]
        
for _ in range(q):
    l , r = map(int,input().split())
    print(rui[r] - rui[l-1])

Solution (Python):
def solve():
    n_max = 10 ** 5
    is_prime = sieve(n_max)
    is_like_2017 = [False] * (n_max+1)

    for i in range(n_max+1):
        if is_prime[i] and is_prime[(i+1)//2]:
            is_like_2017[i] = True

    l = [0] * (n_max+1)
    r = [0] * (n_max+1)
    for i in range(1,n_max+1):
        if is_like_2017[i]:
            l[i] = l[i-1] + 1
        else:
            l[i] = l[i-1]

    for i in range(n_max-1,-1,-1):
        if is_like_2017[i]:
            r[i] = r[i+1] + 1
        else:
            r[i] = r[i+1]
    
    r.append(r[-1])

    Q = int(input())
    ans = []
    for i in range(Q):
        mn, mx = map(int,input().split())
        ans.append(l[-1] - l[mn-1] - r[mx+1])
    
    print(*ans, sep='\n')




def sieve(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False

    p = 0
    for i in range(2,n+1):
        if is_prime[i]:
            p = i
            for j in range(p+p, n+1, p):
                is_prime[j] = False
        
        if p * p > n:
            break

    return is_prime

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import itertools
input = sys.stdin.readline
Q = int(input())
l = []
r = []
for i in range(Q) :
    p, q = map(int,input().split())
    l.append(p)
    r.append(q)

def get_primenumber(number):
    prime_list = []
    search_list = list(range(2,number+1))
    while True:
      if search_list[0]**2 > number:
        prime_list.extend(search_list)
        break
      else:
        head_num = search_list[0]
        prime_list.append(head_num)
        search_list.pop(0)
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

primes = get_primenumber(10**5+1)
like2017 = [0 for _ in range(10**5+1)]

for p in primes :
    if (p+1)//2 in primes :
        like2017[p] = 1

like2017s = list(itertools.accumulate(like2017))

for i in range(Q) :
    print(like2017s[r[i]] - like2017s[l[i]-1])

Solution (Python):
MAX = 10**5 + 1

def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return is_prime
a = primes(MAX)
prime = [0]*MAX
for i in range(1,MAX,2):
    if a[i] == 1 and a[int((i+1)/2)] == 1:
        prime[i] = 1

tmp = 0
csum = [0]*MAX
for i in range(MAX):
    if prime[i] == 1:
        tmp += 1
    csum[i] = tmp
csum.pop()


Q = int(input())
lr = []
for i in range(Q):
    lr.append(list(map(int,input().split())))
for i in range(Q):
    print(csum[lr[i][1]]-csum[lr[i][0]-1])

Solution (Python):
Q = int(input())
R = 10**5 + 10

def getPrimes():
    isPrime = [True] * R
    ret = []
    for i in range(2, R):
        if not isPrime[i]:
            continue
        ret.append(i)
        for j in range(i, R, i):
            isPrime[j] = False
    return set(ret)

P = getPrimes()

def isOk(n):
    return n in P and (n + 1) // 2 in P

A = [0] * R
for i in range(R):
    if isOk(i):
        A[i] += 1

for i in range(1, R):
    A[i] += A[i - 1]

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

print(*ans, sep='\n')

Solution (Python):
n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=sorted(list(primes))
checker0=[0]*(n+1)
checker=[0]*(n+1)
for p in primes:
    checker0[p]=1
    if p%2==1 and checker0[(p+1)//2]==1:
        checker[p]=1

import numpy as np
cumcheck=np.cumsum(checker)

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

Solution (Python):

p = [1]*100000
p[0] = 0
p[1] = 0
p[2] = 1
for i in range(3,100000):
    if i%2==0:
        p[i]=0
    if p[i]==1:
        j = i + i
        while j < 100000:
            p[j] = 0
            j += i
a = [0]*100000
for i in range(2,100000):
    if i % 2 ==0:
        continue
    if p[i] and p[(i+1)//2]:
        a[i] = 1
s = [0]*100001
for i in range(2,100000):
    s[i+1]=s[i]+a[i]

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

Solution (Python):

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

s=[0]*(10**5+1)
c=0

for i in range(3,10**5+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        c+=1
    s[i]=c
for i in range(int(input())):
    l,r=map(int,input().split())
    print(s[r]-s[l-1])

Solution (Python):
from itertools import accumulate
import sys
input = lambda: sys.stdin.readline().rstrip()


def eratosthenes(n):
    is_prime = [1] * (n + 1)

    is_prime[0] = 0
    is_prime[1] = 0

    ans = [0] * (n+1)

    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = 0

    return is_prime


MAX = 10 ** 5


is_prime = eratosthenes(MAX)

a = [0] * (MAX+1)
for i in range(MAX+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1

s = list(accumulate(a))


Q = int(input())

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

Solution (Python):

p = [1]*100000
p[0] = 0
p[1] = 0
p[2] = 1
for i in range(3,100000):
    if i%2==0:
        p[i]=0
    if p[i]==1:
        j = i + i
        while j < 100000:
            p[j] = 0
            j += i
a = [0]*100000
for i in range(2,100000):
    if i % 2 ==0:
        continue
    if p[i] and p[(i+1)//2]:
        a[i] = 1
s = [0]*100001
for i in range(2,100000):
    s[i+1]=s[i]+a[i]

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

Solution (Python):
q=int(input())
import math
import numpy as np
def is_prime(n):
    if n==1:return False
    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False
    return True
def is_is_prime(n):
    an=0
    if is_prime((n+1)//2)==True:
        if is_prime(n)==True:
            an=1
    return an
ko=[]
for i in range(1,10**5,2):
    ko.append(is_is_prime(i))

koko=np.cumsum(ko)

for i in range(q):
    l,r=map(int,input().split()) 
    if l==1:
        ans=koko[(r-1)//2]-koko[(l-1)//2]
    else:
        ans=koko[((r-1)//2)]-koko[((l-1)//2)-1]
    print(ans)

Solution (Python):
from itertools import accumulate
import sys
input = lambda: sys.stdin.readline().rstrip()

MAX = 10 ** 5

def eratosthenes(n):
    is_prime = [1] * (n+1)
    is_prime[0] = 0
    is_prime[1] = 0

    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = 0
    return is_prime        


Q = int(input())

is_prime = eratosthenes(MAX)

a = [0] * (MAX+1)
for i in range(MAX+1):
    if is_prime[i] and is_prime[(i+1)//2]:
        a[i] = 1
s = a
s = list(accumulate(s))

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

Solution (Python):
import sys
input = sys.stdin.readline


import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random



from bisect import bisect_left, bisect_right, insort_left, insort_right







'''
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  
def grid(n): return [s_list() for _ in range(n)]

def dfs(G, v):
    global time, first_order,seen,last_order
    time += 1
    first_order[v-1] = time   

    seen[v-1] = True 
    
    for next_v in G[v]:
        if seen[next_v-1]:
            continue
        dfs(G, next_v)

    time += 1
    last_order[v - 1] = time  
'''

def main():

    def is_prime(n):
        if n == 1:
            return False
        for i in range(2, int(n**0.5)+1):
            if n % i == 0:
                return False
        return True

    Q = int(input())
    task = []
    m = 10**20
    M = 0
    for i in range(Q):
        task.append(list(map(int, input().split())))
        m = min(task[i][0], m)
        M = max(task[i][1], M)

    A = [0]
    count = 0
    for i in range(m, M+1):
        if i % 2 != 0:
            if is_prime((i+1)/2) == True and is_prime(i) == True:
                count += 1
                A.append(count)
            else:
                A.append(count)
        else:
            A.append(count)


    for i in range(Q):
        ans = A[task[i][1]-m +1] -A[task[i][0]-m]
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = 10**5+1
    p = 2
    f = [1]*(n+1)
    f[0] = 0
    f[1] = 0
    while p <= n:
        while p <= n and not f[p]:
            p += 1
        j = 2*p
        while j <= n:
            f[j] = 0
            j += p
        p += 1
    s = [1 if f[i] and f[(i+1)>>1] and i&1 else 0 for i in range(n+1)]
    for i in range(n):
        s[i+1] += s[i]
    q = I()
    for _ in range(q):
        l,r = LI()
        print(s[r]-s[l-1])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
import math
input = sys.stdin.readline


def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    P = []

    for i in range(65):
        prime = min(A)

        if prime > math.sqrt(limit):
            break

        P.append(prime)
        for j in range(limit):
            if j >= len(A):
                break
            if A[j] % prime == 0:
                A.pop(j)
                continue

    for a in A:
        P.append(a)

    return P


def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return True
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    
    return None


MAX = 10 ** 5
prime_list = eratosthenes(MAX)
cumsum = [0] * ((MAX + 1) // 2)
cnt = 0

for i in range(1, MAX, 2):
    if binary_search(prime_list, i) and binary_search(prime_list, (i + 1) / 2):
        cnt += 1
    cumsum[(i - 1) // 2] = cnt

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    if l == 1:
        ans = cumsum[(r - 1) // 2]
    else:
        ans = cumsum[(r - 1) // 2] - cumsum[(l - 3) // 2]
    print(ans)

Solution (Python):
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        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]]

tmp = 0
MAX = 100000
prime = primes(MAX)
a = [0 for _ in range(MAX+1)]
for i in range(MAX+1):
    if i%2 == 0:
        continue
    elif i in prime and int((i+1)/2) in prime:
        a[i] = 1

s = [0 for _ in range(MAX+2)]
for i in range(MAX+1):
    s[i+1] = s[i] + a[i]


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

Solution (Python):
import random
def is_prime(q, k=5):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

q = int(input())
l, r = [0]*q, [0]*q
for i in range(q):
    il, ir = map(int, input().split())
    l[i], r[i] = il, ir

cnt = [0] * (10**5+1)
cnt[0], cnt[1], cnt[2] = 0, 0, 0
for i in range(3, 10**5+1):
    if i % 2 == 0:
        cnt[i] = cnt[i-1]
    else:
        if is_prime(i):
            if is_prime((i+1)//2):
                cnt[i] = cnt[i-1] + 1
            else:
                cnt[i] = cnt[i-1]
        else:
            cnt[i] = cnt[i-1]

for i in range(q):
    print(cnt[r[i]] - cnt[l[i]-1])

Solution (Python):
import random
def is_prime(q, k=5):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

q = int(input())
l, r = [0]*q, [0]*q
for i in range(q):
    il, ir = map(int, input().split())
    l[i], r[i] = il, ir

cnt = [0] * (10**5+1)
cnt[0], cnt[1], cnt[2] = 0, 0, 0
for i in range(3, 10**5+1):
    if i % 2 == 0:
        cnt[i] = cnt[i-1]
    else:
        if is_prime(i):
            if is_prime((i+1)//2):
                cnt[i] = cnt[i-1] + 1
            else:
                cnt[i] = cnt[i-1]
        else:
            cnt[i] = cnt[i-1]

for i in range(q):
    print(cnt[r[i]] - cnt[l[i]-1])

Solution (Python):
import math

def is_prime(n):
  if n == 1: return False
  

  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      
      return False
  return True
  
Q=int(input())
L=[0]*100000
S=[0]*100001
for i in range(100000):
  if is_prime(i+1) and is_prime((i+2)/2):
    L[i]=1
L[1]=0    
for i in range(len(L)):
  S[i+1]=S[i]+L[i]
  

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

Solution (Python):
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(10**5):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


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

if __name__ == '__main__':
    main()

Solution (Python):









import sys



ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    q = int(input())
    prime = [False] * 100001
    count = [0] * 100001
    prime[2] = True

    for i in range(3, 100001, 2):
        for j in range(3, int(i**0.5)+1, 2):
            if i % j == 0:
                break
        else:
            prime[i] = True

    for i in range(3, 100001):
        count[i] = count[i-1]
        if i % 2 == 1 and prime[i] and prime[(i+1)//2]:
            count[i] += 1

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

if __name__ == '__main__':
    main()

Solution (Python):

from bisect import bisect_left, bisect_right
prime = []
like_2017 = []

def sieve(n):
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
            if (i+1)//2 in prime:
                like_2017.append(i)
                
sieve(100000)
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(bisect_right(like_2017, r)-bisect_left(like_2017, l))

Solution (Python):
from itertools import accumulate

def primes(n):
  prime = ([False]*2) + ([True]*(n-2))
  for i in range(2, n):
    if prime[i]:
      for j in range(i*2, n, i):
        prime[j] = False
  return prime

MAX = (10**5)+1
is_prime = primes(MAX)
q = int(input())
A = [1 if is_prime[i] and is_prime[(i + 1)//2] else 0 for i in range(MAX)]
S = [0] + list(accumulate(A))

Q = []
Q_append = Q.append
for _ in range(q):
    l, r = map(int, input().split())
    Q_append((l, r))

for qi in Q:
    print(S[qi[1]+1]-S[qi[0]])

Solution (Python):
import math
from itertools import accumulate

def is_prime(n):
  if n == 1: return False
  for k in range(2, int(math.sqrt(n))+1):
    if n % k == 0: return False
  return True

MAX = (10**5)+1
q = int(input())
A = [1 if is_prime(i)and is_prime((i + 1)//2) else 0 for i in range(MAX) ]
S = [0] + list(accumulate(A))

Q =[]
Q_append = Q.append
for _ in range(q):
    l, r = map(int, input().split())
    Q_append((l, r))

for qi in Q:  
    print(S[qi[1]+1]-S[qi[0]])

Solution (Python):
import sys

def PrimeNumber(max_number):
    
    is_prime = [True] * (max_number + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(max_number**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, max_number + 1, i):
            is_prime[j] = False

    return is_prime


prime_checker = PrimeNumber(10**5)




like_2017 = [0] * (10**5+1)

for i in range(1, 10 ** 5 +1, 2):
    if prime_checker[i] == True and prime_checker[(i + 1) // 2]:
        like_2017[i]=1






sum_like_2017 = [0] * (10**5+1)


for i in range(10 ** 5):
    sum_like_2017[i+1] = sum_like_2017[i] + like_2017[i]





Q = int(input())
for i in range(Q):
    start, end = map(int, input().split())
    print(sum_like_2017[end+1] - sum_like_2017[start])

Solution (Python):
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
        if i*i>n:
            break
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime

from sys import stdin
def main():
    
    readline=stdin.readline
    Q=int(readline())
    l=[0]*Q
    r=[0]*Q
    for i in range(Q):
        l[i],r[i]=map(int,readline().split())

    is_prime=primes(10**5)
    S=[0]*(10**5+1)
    for n in range(3,10**5+1):
        S[n]=S[n-1]
        if is_prime[n] and is_prime[(n+1)//2]:
            S[n]+=1

    for i in range(Q):
        print(S[r[i]]-S[l[i]-1])
if __name__=="__main__":
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(1, 10**5, 2):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        if l==1:
            print(res[r])
        elif res[l]==res[l-2]:
            print(res[r]-res[l])
        else:
            print(res[r]-res[l]+1)

if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(1, 10**5, 2):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        if l==1:
            print(res[r])
        elif res[l]==res[l-2]:
            print(res[r]-res[l])
        else:
            print(res[r]-res[l]+1)

if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(10**5):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


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

if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc084/tasks/abc084_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p
    
    p = primecheck(10**5)
    cnt = 0
    res = [0]*(10**5)
    for i in range(10**5):
        if p[i]==p[(i+1)//2]==1:
            cnt += 1
        res[i] = cnt


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

if __name__ == '__main__':
    main()

Solution (Python):
import math
n = [0,0,1] + [1 for _ in range(10**5-2)]

def check_prime(x):
    for i in range(x*2,10**5+1,x):
        n[i] = 0

check_prime(2)
for i in range(3,int(math.sqrt(10**5))+1,2):
    check_prime(i)

c = [0 for _ in range(10**5+1)]
for i in range(1,10**5+1):
    c[i] = c[i-1] + (n[i] * n[(i+1)//2])

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

Solution (Python):
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])

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

prime = prime_list(10**5)
like = [0 for i in range(10**5+1)]
for i in range(3,10**5+1,2):
    if prime[i] and prime[(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])

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

prime = prime_list(10**5)
like = [0 for i in range(10**5+1)]
for i in range(3,10**5+1,2):
    if prime[i] and prime[(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])

Solution (Python):
from math import sqrt,ceil
n = int(int(1e5))

def prime():
    d = [True] * (n+1)
    d[0] = False
    d[1] = False
    for i in range(2,ceil(sqrt(n+1))):
        if d[i] == True:
            j = 2
            while i * j <= n:
                d[i*j] = False
                j += 1
    return d
d = prime()

cum = [0] * (n + 1)
for i in range(1,n+1):
    cum[i] = cum[i-1]
    if i % 2 == 1:
        if d[i] == True and d[(i+1)//2] == True:
            cum[i] += 1

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

Solution (Python):
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
Q = int(input())
ans = [0] * (10**5+1)
prime = primes(10**5)
for i in range(1,10**5+1):
    if prime[i] == 1 and prime[(i+1)//2] == 1:
        ans[i] = ans[i-1] + 1
        continue
    ans[i] = ans[i-1]
for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Solution (Python):
import math
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
Q = int(input())
ans = [0] * (10**5+1)
prime = [0] * (10**5+1)
for i in range(1,10**5+1):
    if is_prime(i):
        prime[i] = 1
        if prime[(i+1)//2] == 1:
            ans[i] = ans[i-1] + 1
            continue
    ans[i] = ans[i-1]
disp_ans = 0
for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Solution (Python):
import math
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True
Q = int(input())
ans = [0] * (10**5+1)
prime = [0] * (10**5+1)
for i in range(1,10**5+1):
    if is_prime(i):
        prime[i] = 1
        if prime[(i+1)//2] == 1:
            ans[i] = ans[i-1] + 1
            continue
    ans[i] = ans[i-1]
disp_ans = 0
for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r]-ans[l-1])

Solution (Python):

import math


def is_sosu(n):

    if n == 2:
        return True

    if n < 2 or n % 2 == 0:
        return False

    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False

    return True


def similar_to_2017(n):
    if is_sosu(n) and is_sosu((n + 1) / 2):
        return True

    return False


def main():
    q = int(input())
    in_target = [tuple(map(int, input().split())) for i in range(q)]

    similar_to_2017s = {}
    for i in range(1, 100001, 2):
        if similar_to_2017(i):
            similar_to_2017s[i] = 1 + similar_to_2017s.get(i - 2, 0)
        else:
            similar_to_2017s[i] = similar_to_2017s.get(i - 2, 0)

    for target in in_target:
        cnt = similar_to_2017s.get(target[1], 0) - similar_to_2017s.get(target[0] - 2, 0)

        print(cnt)


if __name__ == '__main__':
    main()