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())
info = [list(map(int,input().split())) for i in range(q)]

def prime_table(n):
  list = [True for _ in range(n + 1)]
  i = 2
  while i * i <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1

  table = [i for i in range(n + 1) if list[i] and i >= 2]
  return table

li = prime_table(10**5)

isPrime = [False]*(10**5+1)
for i in li:
  isPrime[i] = True

isLikeNum = [0]*(10**5+1)
for i in range(1,10**5+1,2):
  if isPrime[i] and isPrime[(i+1)//2]:
    isLikeNum[i] = 1

ruiseki = [0]*(10**5+1)
for i in range(1,10**5+1):
  ruiseki[i] = ruiseki[i-1] + isLikeNum[i]
#print(ruiseki)

for i in range(q):
  print(ruiseki[info[i][1]]-ruiseki[info[i][0]-1])

Submission status: Accepted

Solution code:
n=10**5+2
#n=100
p=[0]*n
ac=[0]*n
def prime_list(x):
    for i in range(2,x+1):
        flg=True
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                flg=False
        if flg==True:
            p[i]=1

prime_list(n)
#print(p)
pre=0
for i in range(n):
    if p[i]==1 and p[int((i+1)/2)]==1 and i%2==1:
        k=1
    else:
        k=0
    pre+=k
    ac[i]=pre

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

Submission status: Accepted

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

N = 10 ** 5
pn = sieve(N + 1)

dp = [0] * (N + 1)
for i in pn:
    if (i + 1) // 2 in pn:
        dp[i] += 1
        
for i in range(1, N + 1):
    dp[i] += dp[i - 1] 
        
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(dp[r] - dp[l - 1])

Submission status: Accepted

Solution code:
a=[True]*(10**5+1)
for i in range(2,int(10**2.5)+1):
    if a[i]:
        for j in range(i+i,10**5+1,i):
            a[j]=False
s=[0]*(10**5+1)
c=0
for i in range(3,10**5+1):
    if a[i] and a[(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])

Submission status: Accepted

Solution code:
import bisect

Q = int(input())

L = [1 for i in range(100001)]
L[0] = 0
L[1] = 0
for i in range(100001):
	if L[i] == 1:
		c = 2
		while True:
			if i * c <= 100000:
				L[i * c] = 0
				c += 1
			else:
				break
p2017 = []
for i in range(3, 100001):
	if i % 2 != 0:
		if L[i] == 1 and L[int((i + 1) // 2)] == 1:
			p2017.append(i)


for i in range(Q):
	l, r = list(map(int, input().split()))
	a = bisect.bisect_left(p2017, l)
	b = bisect.bisect_right(p2017, r)
	print(b - a)

Submission status: Accepted

Solution code:
#084-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
B=[1]*(10**5+2)
B[0]=0
B[1]=0
for i in range(2,10**5+2):
    if B[i]==1:
        for j in range(i+i,10**5+2,i):
            B[j]=0
J=[0]*(10**5+1)
for i in range(1,10**5+1,2):
    if B[i]*B[(i+1)//2]==1:
        J[i]=1
for i in range(1,10**5+1):
    J[i]+=J[i-1]
q=I()
for i in range(q):
    l,r=IL()
    print(J[r]-J[l-1])

Submission status: Accepted

Solution code:
prime = [0,0] + [1]*100010
for i in range(int((100010)**0.5)):
    if prime[i]:
        for j in range(i*2,100010,i):
            prime[j] = 0
alike = [(prime[i] and prime[(i+1)//2]) for i in range(100001)]
for i in range(1,100001): alike[i] += alike[i-1]

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

Submission status: Accepted

Solution code:
from bisect import *
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
a=[i for i in range(2,10**5)if is_prime(i)and is_prime((i+1)//2)]
#print(a)
n=int(input())
for i in range(n):
    c,d=map(int,input().split())
    print(bisect_right(a,d)-bisect_left(a,c))

Submission status: Accepted

Solution code:
from math import sqrt


def _2017_like_number(Q: int, queries: list) -> list:
    N = 10 ** 5
    prime_numbers, prime_count = [], 0

    def is_prime(n: int) -> bool:
        if n < 2:
            return False

        sq = int(sqrt(n)) + 1
        for p in prime_numbers:
            if sq < p:
                break
            if n % p == 0:
                return False

        return True

    def is_prime_use_list(n: int) -> bool:
        l, r = 0, prime_count
        while r - l > 1:
            m = (l + r) // 2

            if prime_numbers[m] <= n:
                l = m
            else:
                r = m

        return prime_numbers[l] == n

    S = [0] * (N + 1)
    for i in range(0, N):
        S[i + 1] = S[i]

        if is_prime(i + 1):
            prime_numbers.append(i + 1)
            prime_count += 1
        else:
            continue

        if is_prime_use_list((i+2)//2):
            S[i + 1] += 1

    return [S[r] - S[l - 1] for l, r in queries]


if __name__ == "__main__":
    Q = int(input())
    queries = [tuple(int(s) for s in input().split()) for _ in range(Q)]
    ans = _2017_like_number(Q, queries)
    for a in ans:
        print(a)

Submission status: Accepted

Solution code:
from itertools import accumulate

# 入力
Q = int(input())
l, r = zip(*(map(int, input().split()) for _ in range(Q)))

# エラトステネスのふるいにより、素数表を作成する
is_prime = [i >= 2 for i in range(10**5 + 1)]
for i in range(2, 10**5 + 1):
    if is_prime[i]:
        for j in range(2 * i, 10**5 + 1, i):
            is_prime[j] = False

# i以下の2017に似た数の累積和を求める
dp = list(
    accumulate(
        range(10**5 + 1),
        lambda acc, i: (
            acc + 1 if is_prime[i] and is_prime[(i + 1) // 2] else
            acc
        )
    )
)

# 累積和を用いて各クエリに回答する
ans = '\n'.join(
    map(
        str,
        (dp[b] - dp[a - 1] for a, b in zip(l, r))
    )
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
import math
N = 10**5

Q = int(input())


def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める."""
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


_primes = eratosthenes(N)

primes = [False] * (10**5 + 1)

for p in _primes:
    primes[p] = True

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

for p in _primes:
    if primes[(p + 1) // 2]:
        like_2017[p] = True


c = 0
C = [0]
for i in range(1, 10**5 + 1):
    if like_2017[i]:
        c += 1
    C.append(c)


for _ in range(Q):
    left, right = map(int, input().split())
    print(C[right] - C[left - 1])

Submission status: Accepted

Solution code:
from collections import defaultdict

def prime_gen(limit):
    dd = defaultdict(list)
    for x in range(2, limit + 1):
        if x in dd:
            for y in dd[x]:
                dd[y + x].append(y)
        else:
            yield x
            dd[x * x].append(x)

if __name__ == '__main__':
    ps = set(prime_gen(100000))
    like2017s = {n for n in ps if (n + 1) // 2 in ps}
    acc = [0] * 100001
    for i in range(3, 100001):
        acc[i] = acc[i - 1]
        if i in like2017s:
            acc[i] += 1

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
if __name__ == "__main__":
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(100001)]
    for i in range(1,100001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l-1])

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(100001)]
    for i in range(1,100001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l-1])

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def check(n):
    if n == 1:
        return False
    i = 2
    while i*i <= n:
        if n%i == 0:
            return False
        i += 1
    return True
f = [0 for i in range(100001)]
for i in range(1,100001):
    f[i] += f[i-1]
    if check(i):
        if check((i+1)//2):
            f[i] += 1
q = I()
for i in range(q):
    l,r = LI()
    print(f[r]-f[l-1])

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve

Submission status: Accepted

Solution code:
import sys

def f(d):
    num = 3
    p = [2]
    c = 0
    while num <= 10**5:
        m = int(num**0.5)
        while m > 1 and num % m != 0:
            m -= 1
        if m == 1:
            p.append(num)
            if (num+1)//2 in p:
                c += 1
        d[num] = c
        num += 2
    return d


def main():
    input = sys.stdin.readline
    Q = int(input())
    d = {1: 0, 2: 0}
    d = f(d)
    for _ in range(Q):
        l, r = map(int, input().split())
        l = max(l - 2, 1)
        print(d[r] - d[l])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Q = int(input())
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**5)

like2017 = [x for x in PS if (x+1) // 2 in PS]

import bisect
for i in range(Q):
  l, r = map(int, input().split())
  li = bisect.bisect_left(like2017, l-1)
  ri = bisect.bisect_left(like2017, r+1)
  print(ri - li)

Submission status: Accepted

Solution code:
def primes(N):
    is_prime = {i: True for i in range(2, N+1)}
    for i in range(2, N+1):
        if is_prime[i]:
            if i**2 <= N:
                for j in range(i**2, N+1, i):
                    is_prime[j] = False
    return is_prime


def main():
    is_prime = primes(10**5)
    cumsum = [0] * (10**5)
    for i in range(3, 10**5):
        cumsum[i] = cumsum[i-1]
        if is_prime[i] and is_prime[(i+1)//2]:
            cumsum[i] += 1
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(cumsum[r] - cumsum[l-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MAX_PRIME = 10**5
is_prime = [1] * MAX_PRIME
primes = set()
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0
yearlike = set()
for i in range(1,10**5):
    if i in primes and (i+1)//2 in primes:
        yearlike.add(i)
cum = [0] * 2*10**5
for i in range(10**5+5):
    cum[i+1] = cum[i] + int(i in yearlike)
q = int(input())
query = [tuple(map(int, input().split())) for _ in range(q)]
for l, r in query:
    print(cum[r+1] - cum[l])

Submission status: Accepted

Solution code:
from itertools import accumulate
N = 100000
prime = [True for _ in range(N+1)]
prime[0] = False
prime[1] = False
i = 2
for i in range(N+1):
    if prime[i]:
        for j in range(2*i, N+1, i):
            prime[j] = False
prime2 = [0 for _ in range(N+1)]
for i in range(N+1):
    if prime[i] and prime[(i+1)//2]:
        prime2[i] = 1
acc = list(accumulate(prime2))

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

Submission status: Accepted

Solution code:
import math
import numpy as np
Q = int(input())
LR = []
for _ in range(Q):
    LR.append(list(map(int, input().split())))

rmax = max(r for l, r in LR)
# primes
primes = np.ones(1 + rmax, int)
primes[4::2] = 0
for i in range(3, 1 + int(math.sqrt(rmax)), 2):
    if primes[i]:
        primes[2*i::i] = 0
# like 2017
for i in range(rmax, 0, -2):
    if primes[i] and not primes[(i + 1) // 2]:
        primes[i] = 0
primes[:3] = 0
acc = np.cumsum(primes)
for l, r in LR:
    ans = acc[r] - acc[l - 1]
    print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np
Q = int(input())
LR = []
for _ in range(Q):
    LR.append(list(map(int, input().split())))

rmax = max(r for l, r in LR)
primes = np.ones(1 + rmax, int)
for i in range(2, 1 + int(math.sqrt(rmax))):
    if primes[i]:
        primes[2*i::i] = 0
primes[:2] = 0
# like 2017
for i in range(rmax, 0, -2):
    if primes[i] and not primes[(i + 1) // 2]:
        primes[i] = 0
primes[2] = 0
acc = np.cumsum(primes)
for l, r in LR:
    ans = acc[r] - acc[l - 1]
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

ans=defaultdict(int)
d=defaultdict(int)
p_list=[2]

p=2
n=10**5

while p<=n:
    m=2*p
    while m<=n:
        d[m]=1
        m+=p
    p+=1
    while d[p]!=0:
        p+=1
        if p>n:
            break
    p_list.append(p)

pp=defaultdict(int)

for i in p_list:
    if d[(i+1)//2]==0:
        pp[i]=1

cnt=0
for i in range(1,10**5+1,2):
    if pp[i]==1:
        cnt+=1
    ans[i]=cnt

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

Submission status: Accepted

Solution code:
la = 10**5+10
#la = 100

A = [1 for i in range(la)]
A[0] = 0
A[1] = 0
for i in range(2, int(la**0.5) + 2) :
    j = 2
    while j*i <= len(A)-1 :
        A[j*i] = 0
        j += 1
#print(A)

q = int(input())
L = [list(map(int, input().split())) for i in range(q)]

B = [0 for i in range(la)]

for i in range(3, la) :
    if A[i] == 1 and A[(i+1)//2] == 1 :
        B[i] += 1
#print(B)

for i in range(1, len(B)) :
    B[i] += B[i-1]


for i in range(q) :
    print(B[L[i][1]] - B[L[i][0]-1])

Submission status: Accepted

Solution code:
import sys,math,itertools
input = sys.stdin.readline
Q = int(input())
query = [list(map(int,input().split())) for i in range(Q)]

def is_prime(n):
        if n <= 0:return None
        if n == 1:return False
        sup = math.floor(pow(n,1/2))
        for i in range(2,sup+1):
                if n % i == 0:
                        return False
        return True

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

for i in range(10**5,-1,-1):
        if prime[i] and i % 2 == 1 and prime[(i+1)//2]:
                pass
        else:
                prime[i] = 0

acc = list(itertools.accumulate(prime))
for l,r in query:
        print(acc[r]-acc[l-1])

Submission status: Accepted

Solution code:
import math
import itertools
Q = int(input())
query = [list(map(int,input().split())) for i in range(Q)]

def is_prime(n):
        if n <= 0:return None
        if n == 1:return False
        sup = math.floor(pow(n,1/2))
        for i in range(2,sup+1):
                if n % i == 0:
                        return False
        return True

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

for p,bit in enumerate(prime[::-1]):
        p = len(prime)-1 - p
        if bit and p % 2 == 1 and prime[(p+1)//2]:
                pass
        else:
                prime[p] = 0

acc = list(itertools.accumulate(prime))
for l,r in query:
        print(acc[r]-acc[l-1])

Submission status: Accepted

Solution code:
import math
import itertools
Q = int(input())
query = [list(map(int,input().split())) for i in range(Q)]

def is_prime(n):
        if n <= 0:return None
        if n == 1:return False
        sup = math.floor(pow(n,1/2))
        for i in range(2,sup+1):
                if n % i == 0:
                        return False
        return True

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

for i in range(10**5,-1,-1):
        if prime[i] and i % 2 == 1 and prime[(i+1)//2]:
                pass
        else:
                prime[i] = 0

acc = list(itertools.accumulate(prime))
for l,r in query:
        print(acc[r]-acc[l-1])

Submission status: Accepted

Solution code:
# D
from math import sqrt
def sieve(n:int)->list:
    """エラトステネスの篩"""
    if n<2:  return [False]*(n+1)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(sqrt(n))+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    
    return is_prime


N = int(1e5)
is_prime = sieve(N)
# like-2017
cnt = [0]*(N+1)
for i in range(1, N+1):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
    
import sys
Q = sys.stdin.readline()
for l,r in (map(int, line.split()) for line in sys.stdin.readlines()):
    print(cnt[r] - cnt[l-1])

Submission status: Accepted

Solution code:

import math

isprime = None
 
def sieve(n):
    global isprime
 
    if n < 2:
        isprime = [False] * (n + 1)
        return
 
    isprime = [True if i % 2 != 0 else False for i in range(n + 1)]
    isprime[0] = isprime[1] = False
    isprime[2] = True
 
    from math import sqrt, ceil
 
    for i in range(3, int(sqrt(n)) + 1):
        if isprime[i] == True:
            for j in range(i + i, n + 1, i):
                isprime[j] = False

sieve(10**5+1)


accm = [0] * (10**5+1)
for i in range(3, 10**5+1):
    accm[i] += accm[i-1]
    if isprime[i] and isprime[(i+1)//2]:
        accm[i] += 1

import sys
Q = int(input())
# for i in range(Q):
#     l,r = map(int,input().split())
for l,r in ( map(int, line.split())  for line in sys.stdin.readlines() ):

    if isprime[l] and isprime[(l+1)//2]:
        l-=1
    if isprime[r] and isprime[(r+1)//2]:
        r+=1

    print( accm[r] - accm[l] )

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


import math

def mirror_prime(n):
    answer = True
    # Test 0 and 1
    if n==0 or n==1:
        answer = False
    # End if

    # Test even numbers
    if n != 2 and n%2==0:
        answer= False
    # End if

    # Test if there is a proper odd divisor
        for d in range (3, int(math.sqrt(n))+1, 2):
            if n%d==0:
                answer=False
            # End if
        # End for



    #Reverse n
    mirror_n = int(str(n)[::-1])
    mirror_answer = True

    # Test 0 and 1
    if mirror_n==0 or mirror_n==1:
        mirror_answer = False

def primes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

# BIT = Bit(10**5+1)

isprime = None
 
def sieve(n):
    global isprime
 
    if n < 2:
        isprime = [False] * (n + 1)
        return
 
    isprime = [True if i % 2 != 0 else False for i in range(n + 1)]
    isprime[0] = isprime[1] = False
    isprime[2] = True
 
    from math import sqrt, ceil
 
    for i in range(3, int(sqrt(n)) + 1):
        if isprime[i] == True:
            for j in range(i + i, n + 1, i):
                isprime[j] = False

# plist = primes(10**5+1)
sieve(10**5+1)


accm = [0] * (10**5+1)
for i in range(3, 10**5+1):
    accm[i] += accm[i-1]
    # if mirror_prime(i) and mirror_prime((i+1)//2):
    if isprime[i] and isprime[(i+1)//2]:
        accm[i] += 1

Q = int(input())
for i in range(Q):
    l,r = map(int,input().split())
    # if mirror_prime(l) and mirror_prime((l+1)//2):
    if isprime[l] and isprime[(l+1)//2]:
        l-=1
    # if mirror_prime(r) and mirror_prime((r+1)//2):
    if isprime[r] and isprime[(r+1)//2]:
        r+=1
    print( accm[r] - accm[l] )