# エラトステネスの篩, 累積和

def make_prime_table(N):

    sieve = [0] * (N + 1)

    sieve[0] = -1

    sieve[1] = -1

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

        if sieve[i] != 0:

            continue

        sieve[i] = i

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

            if sieve[j] == 0:

                sieve[j] = i

    return sieve



max_lr = 10 ** 5



prime_table = make_prime_table(max_lr)



cs = [0] * (max_lr + 1)

for i in range(3, max_lr + 1, 2):

    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:

        cs[i] = 1

for i in range(1, max_lr + 1):

    cs[i] += cs[i - 1]



Q = int(eval(input()))

for _ in range(Q):

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

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

# エラトステネスの篩, 累積和

def make_prime_table(N):

    sieve = list(range(N + 1))

    sieve[0] = -1

    sieve[1] = -1

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

        if sieve[i] != i:

            continue

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

            if sieve[j] == j:

                sieve[j] = i

    return sieve





max_lr = 10 ** 5



prime_table = make_prime_table(max_lr)



cs = [0] * (max_lr + 1)

for i in range(3, max_lr + 1, 2):

    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:

        cs[i] = 1

for i in range(1, max_lr + 1):

    cs[i] += cs[i - 1]



Q = int(eval(input()))

result = []

for _ in range(Q):

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

    result.append(cs[r] - cs[l - 1])

print(('\n'.join(str(i) for i in result)))

# エラトステネスの篩, 累積和
def make_prime_table(N):
    sieve = [0] * (N + 1)
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, N + 1):
        if sieve[i] != 0:
            continue
        sieve[i] = i
        for j in range(i * i, N + 1, i):
            if sieve[j] == 0:
                sieve[j] = i
    return sieve


max_lr = 10**5
prime_table = make_prime_table(max_lr)
cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l - 1]))

# エラトステネスの篩, 累積和
def make_prime_table(N):
    sieve = list(range(N + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(N**0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, N + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10**5
prime_table = make_prime_table(max_lr)
cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]
Q = int(eval(input()))
result = []
for _ in range(Q):
    l, r = list(map(int, input().split()))
    result.append(cs[r] - cs[l - 1])
print(("\n".join(str(i) for i in result)))

-    sieve = [0] * (N + 1) +    sieve = list(range(N + 1)) -    for i in range(2, N + 1): -        if sieve[i] != 0: +    for i in range(2, int(N**0.5) + 1): +        if sieve[i] != i: -        sieve[i] = i -            if sieve[j] == 0: +            if sieve[j] == j: +result = [] -    print((cs[r] - cs[l - 1])) +    result.append(cs[r] - cs[l - 1]) +print(("\n".join(str(i) for i in result)))