def primes(N):

    '''Sieve of Eratosthenes'''

    p = [False, False] + [True] * (N - 1)

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

        if p[i]:

            for j in range(i * 2, N + 1, i):

                p[j] = False

    return p





p, c = primes(10 ** 5), [0]

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

    c.append(c[-1] + 1 if p[i] and p[(i + 1) // 2] else c[-1])



Q = int(eval(input()))

for _ in range(Q):

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

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

def primes(N):

    p = [False, False] + [True] * (N - 1)

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

        if p[i]:

            for j in range(i * 2, N + 1, i):

                p[j] = False

    return p





p, c = primes(10 ** 5), [0]

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

    c.append(c[-1] + 1 if p[i] and p[(i + 1) // 2] else c[-1])



Q = int(eval(input()))

for _ in range(Q):

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

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

def primes(N):
    """Sieve of Eratosthenes"""
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N**0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return p


p, c = primes(10**5), [0]
for i in range(1, 10**5 + 1):
    c.append(c[-1] + 1 if p[i] and p[(i + 1) // 2] else c[-1])
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((c[r] - c[l - 1]))

def primes(N):
    p = [False, False] + [True] * (N - 1)
    for i in range(2, int(N**0.5) + 1):
        if p[i]:
            for j in range(i * 2, N + 1, i):
                p[j] = False
    return p


p, c = primes(10**5), [0]
for i in range(1, 10**5 + 1):
    c.append(c[-1] + 1 if p[i] and p[(i + 1) // 2] else c[-1])
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((c[r] - c[l - 1]))

-    """Sieve of Eratosthenes"""