from itertools import accumulate

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(eval(input()))



l, r = [],[]

for _ in range(q):

    t, tt = list(map(int, input().split()))

    l.append(t)

    r.append(tt)



m_r = max(r)



table = [0] * (m_r + 2)

for i in range(1, m_r + 1, 2):

    if is_prime(i) and is_prime((i + 1) // 2):

        table[i] = 1



c_table = list(accumulate(table))



for i in range(q):

    print((c_table[r[i]] - c_table[l[i]-1]))
from itertools import accumulate



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(eval(input()))



l, r = [],[]

for _ in range(q):

    t, tt = list(map(int, input().split()))

    l.append(t)

    r.append(tt)



m_r = max(r)



table = [0] * (m_r + 2)

for i in range(1, m_r + 1, 2):

    if is_prime(i) and is_prime((i + 1) // 2):

        table[i] = 1



acc_table = list(accumulate(table))



for i in range(q):

    print((acc_table[r[i]] - acc_table[l[i]-1]))
from itertools import accumulate


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(eval(input()))
l, r = [], []
for _ in range(q):
    t, tt = list(map(int, input().split()))
    l.append(t)
    r.append(tt)
m_r = max(r)
table = [0] * (m_r + 2)
for i in range(1, m_r + 1, 2):
    if is_prime(i) and is_prime((i + 1) // 2):
        table[i] = 1
c_table = list(accumulate(table))
for i in range(q):
    print((c_table[r[i]] - c_table[l[i] - 1]))

from itertools import accumulate


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(eval(input()))
l, r = [], []
for _ in range(q):
    t, tt = list(map(int, input().split()))
    l.append(t)
    r.append(tt)
m_r = max(r)
table = [0] * (m_r + 2)
for i in range(1, m_r + 1, 2):
    if is_prime(i) and is_prime((i + 1) // 2):
        table[i] = 1
acc_table = list(accumulate(table))
for i in range(q):
    print((acc_table[r[i]] - acc_table[l[i] - 1]))

-c_table = list(accumulate(table)) +acc_table = list(accumulate(table)) -    print((c_table[r[i]] - c_table[l[i] - 1])) +    print((acc_table[r[i]] - acc_table[l[i] - 1]))