Q = int(eval(input()))

MIN, MAX = 10**18, 0

LR = []

for q in range(Q):

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

    MIN = min(MIN, l)

    MAX = max(MAX, r)

    LR.append((l, r))



from math import sqrt

from itertools import accumulate

lis = [0]*(MAX+1)

search = [2] + [i for i in range(2, MAX+1) if i%2!=0]

lim = sqrt(MAX)

prime = set()

while 1:

    n = search[0]

    if n>=lim:

        break

    prime.add(n)

    if (n+1)//2 in prime:

        lis[n] = 1

    search = [i for i in search if i%n!=0]

for s in search:

    prime.add(s)

    if (s+1)//2 in prime:

        lis[s] = 1

clis = list(accumulate(lis))

for l, r in LR:

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

import sys

def input(): return sys.stdin.readline().strip()

def mapint(): return list(map(int, input().split()))

sys.setrecursionlimit(10**9)



s = set()

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

    if i in s:

        continue

    cnt = 2

    while i*cnt<=10**5+5:

        s.add(i*cnt)

        cnt += 1



from itertools import accumulate



lis = [0]*(10**5+5)

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

    if not i in s and not (i+1)//2 in s:

        lis[i] = 1



lis = list(accumulate(lis))

Q = int(eval(input()))

for _ in range(Q):

    l, r = mapint()

    print((lis[r]-lis[l-1]))
Q = int(eval(input()))
MIN, MAX = 10**18, 0
LR = []
for q in range(Q):
    l, r = list(map(int, input().split()))
    MIN = min(MIN, l)
    MAX = max(MAX, r)
    LR.append((l, r))
from math import sqrt
from itertools import accumulate

lis = [0] * (MAX + 1)
search = [2] + [i for i in range(2, MAX + 1) if i % 2 != 0]
lim = sqrt(MAX)
prime = set()
while 1:
    n = search[0]
    if n >= lim:
        break
    prime.add(n)
    if (n + 1) // 2 in prime:
        lis[n] = 1
    search = [i for i in search if i % n != 0]
for s in search:
    prime.add(s)
    if (s + 1) // 2 in prime:
        lis[s] = 1
clis = list(accumulate(lis))
for l, r in LR:
    print((clis[r] - clis[l - 1]))

import sys


def input():
    return sys.stdin.readline().strip()


def mapint():
    return list(map(int, input().split()))


sys.setrecursionlimit(10**9)
s = set()
for i in range(2, 10**5 + 5):
    if i in s:
        continue
    cnt = 2
    while i * cnt <= 10**5 + 5:
        s.add(i * cnt)
        cnt += 1
from itertools import accumulate

lis = [0] * (10**5 + 5)
for i in range(3, 10**5 + 5, 2):
    if not i in s and not (i + 1) // 2 in s:
        lis[i] = 1
lis = list(accumulate(lis))
Q = int(eval(input()))
for _ in range(Q):
    l, r = mapint()
    print((lis[r] - lis[l - 1]))

-Q = int(eval(input())) -MIN, MAX = 10**18, 0 -LR = [] -for q in range(Q): -    l, r = list(map(int, input().split())) -    MIN = min(MIN, l) -    MAX = max(MAX, r) -    LR.append((l, r)) -from math import sqrt +import sys + + +def input(): +    return sys.stdin.readline().strip() + + +def mapint(): +    return list(map(int, input().split())) + + +sys.setrecursionlimit(10**9) +s = set() +for i in range(2, 10**5 + 5): +    if i in s: +        continue +    cnt = 2 +    while i * cnt <= 10**5 + 5: +        s.add(i * cnt) +        cnt += 1 -lis = [0] * (MAX + 1) -search = [2] + [i for i in range(2, MAX + 1) if i % 2 != 0] -lim = sqrt(MAX) -prime = set() -while 1: -    n = search[0] -    if n >= lim: -        break -    prime.add(n) -    if (n + 1) // 2 in prime: -        lis[n] = 1 -    search = [i for i in search if i % n != 0] -for s in search: -    prime.add(s) -    if (s + 1) // 2 in prime: -        lis[s] = 1 -clis = list(accumulate(lis)) -for l, r in LR: -    print((clis[r] - clis[l - 1])) +lis = [0] * (10**5 + 5) +for i in range(3, 10**5 + 5, 2): +    if not i in s and not (i + 1) // 2 in s: +        lis[i] = 1 +lis = list(accumulate(lis)) +Q = int(eval(input())) +for _ in range(Q): +    l, r = mapint() +    print((lis[r] - lis[l - 1]))