def eratosthenes(n):

    prime = []

    limit = n**0.5

    numbers = [i for i in range(2,n+1)]

    while True:

        p = numbers[0]

        if limit <= p:

            return prime + numbers

        prime.append(p)

        numbers = [i for i in numbers if i%p != 0]



primes = eratosthenes(100000)

numbers = [(p+1)//2 for p in primes]

alike = list(set(primes)&set(numbers))

alike = [2*p-1 for p in alike]

alike.sort()

alike



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

for p in alike:

    cum[p] = 1

import numpy as np

cum = np.array(cum)

cum = np.cumsum(cum)



Q = int(eval(input()))

for i in range(Q):

    l,r = list(map(int,input().split()))

    print((cum[r]-cum[l-1]))

from collections import defaultdict

from bisect import bisect,bisect_left

def eratosthenes(n):

    prime = []

    limit = n**0.5

    numbers = [i for i in range(2,n+1)]

    while True:

        p = numbers[0]

        if limit <= p:

            return prime + numbers

        prime.append(p)

        numbers = [i for i in numbers if i%p != 0]

    return prime

prime = eratosthenes(10**5)

p_d = defaultdict(lambda:0)

prime17 = []

for p in prime:

    p_d[p] = 1

for p in prime:

    if p_d[(p+1)/2] == 1:

        prime17.append(p)



Q = int(eval(input()))

for _ in range(Q):

    l,r = list(map(int,input().split()))

    l = bisect_left(prime17,l)

    r = bisect(prime17,r)

    print((r-l))
def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2, n + 1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i % p != 0]


primes = eratosthenes(100000)
numbers = [(p + 1) // 2 for p in primes]
alike = list(set(primes) & set(numbers))
alike = [2 * p - 1 for p in alike]
alike.sort()
alike
cum = [0] * (10**5 + 1)
for p in alike:
    cum[p] = 1
import numpy as np

cum = np.array(cum)
cum = np.cumsum(cum)
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((cum[r] - cum[l - 1]))

from collections import defaultdict
from bisect import bisect, bisect_left


def eratosthenes(n):
    prime = []
    limit = n**0.5
    numbers = [i for i in range(2, n + 1)]
    while True:
        p = numbers[0]
        if limit <= p:
            return prime + numbers
        prime.append(p)
        numbers = [i for i in numbers if i % p != 0]
    return prime


prime = eratosthenes(10**5)
p_d = defaultdict(lambda: 0)
prime17 = []
for p in prime:
    p_d[p] = 1
for p in prime:
    if p_d[(p + 1) / 2] == 1:
        prime17.append(p)
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    l = bisect_left(prime17, l)
    r = bisect(prime17, r)
    print((r - l))

+from collections import defaultdict +from bisect import bisect, bisect_left + + +    return prime -primes = eratosthenes(100000) -numbers = [(p + 1) // 2 for p in primes] -alike = list(set(primes) & set(numbers)) -alike = [2 * p - 1 for p in alike] -alike.sort() -alike -cum = [0] * (10**5 + 1) -for p in alike: -    cum[p] = 1 -import numpy as np - -cum = np.array(cum) -cum = np.cumsum(cum) +prime = eratosthenes(10**5) +p_d = defaultdict(lambda: 0) +prime17 = [] +for p in prime: +    p_d[p] = 1 +for p in prime: +    if p_d[(p + 1) / 2] == 1: +        prime17.append(p) -for i in range(Q): +for _ in range(Q): -    print((cum[r] - cum[l - 1])) +    l = bisect_left(prime17, l) +    r = bisect(prime17, r) +    print((r - l))