q = int(eval(input()))

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



def prime_table(n):

    list = [True for _ in range(n+1)]

    for i in range(2,int(n**0.5)+1):

        if list[i]:

            j = i*2

            while j<=n:

                list[j] = False

                j += i

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

    return table



table = prime_table(10**5)

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



for i in range(len(table)):

    if table[i]*2-1 in table:

        sim_sum[table[i]*2-1] += 1

for i in range(1,10**5+1):

    sim_sum[i] += sim_sum[i-1]

for l_ in l:

    print((sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)]))
q = int(eval(input()))

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



def prime_table(n):

    list = [True for _ in range(n+1)]

    for i in range(2,int(n**0.5)+1):

        if list[i]:

            j = i*2

            while j<=n:

                list[j] = False

                j += i

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

    return table



table = prime_table(10**5)

table_set = set(table)

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



for p in table:

    if p*2-1 in table_set:

        sim_sum[p*2-1] += 1

for i in range(1,10**5+1):

    sim_sum[i] += sim_sum[i-1]

for l_ in l:

    print((sim_sum[l_[1]]-sim_sum[max(l_[0]-2,0)]))
q = int(eval(input()))
l = [list(map(int, input().split())) for _ in range(q)]


def prime_table(n):
    list = [True for _ in range(n + 1)]
    for i in range(2, int(n**0.5) + 1):
        if list[i]:
            j = i * 2
            while j <= n:
                list[j] = False
                j += i
    table = [i for i in range(n + 1) if list[i] and i >= 2]
    return table


table = prime_table(10**5)
sim_sum = [0] * (10**5 + 1)
for i in range(len(table)):
    if table[i] * 2 - 1 in table:
        sim_sum[table[i] * 2 - 1] += 1
for i in range(1, 10**5 + 1):
    sim_sum[i] += sim_sum[i - 1]
for l_ in l:
    print((sim_sum[l_[1]] - sim_sum[max(l_[0] - 2, 0)]))

q = int(eval(input()))
l = [list(map(int, input().split())) for _ in range(q)]


def prime_table(n):
    list = [True for _ in range(n + 1)]
    for i in range(2, int(n**0.5) + 1):
        if list[i]:
            j = i * 2
            while j <= n:
                list[j] = False
                j += i
    table = [i for i in range(n + 1) if list[i] and i >= 2]
    return table


table = prime_table(10**5)
table_set = set(table)
sim_sum = [0] * (10**5 + 1)
for p in table:
    if p * 2 - 1 in table_set:
        sim_sum[p * 2 - 1] += 1
for i in range(1, 10**5 + 1):
    sim_sum[i] += sim_sum[i - 1]
for l_ in l:
    print((sim_sum[l_[1]] - sim_sum[max(l_[0] - 2, 0)]))

+table_set = set(table) -for i in range(len(table)): -    if table[i] * 2 - 1 in table: -        sim_sum[table[i] * 2 - 1] += 1 +for p in table: +    if p * 2 - 1 in table_set: +        sim_sum[p * 2 - 1] += 1