def get_prime_list(n):

    l = [0 for _ in range(n)]

    i = 1

    while (i < n):

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

            if not (i + 1) % j:

                break

        else:

            l[i] = 1

        i += 1



    return l





n_max = 10**5

is_prime = get_prime_list(n_max)

is_2017 = [0 for _ in range(n_max)]

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

    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:

        is_2017[i - 1] = 1



s = [0]

for i in range(n_max):

    s.append(s[i] + is_2017[i])



q = int(eval(input()))

for _ in range(q):

    li, ri = list(map(int, input().split()))

    print((s[ri] - s[li - 1]))
def erat(n):

    l = [0, 0] + [1 for _ in range(n - 1)]

    i = 2

    while (i < n + 1):

        if l[i] == 1:

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

                l[j] = 0

        i += 1



    return l





n_max = 10**5

is_prime = erat(n_max)

is_2017 = [0 for _ in range(n_max + 1)]

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

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

        is_2017[i] = 1



s = [0]

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

    s.append(s[i - 1] + is_2017[i])



q = int(eval(input()))

for _ in range(q):

    li, ri = list(map(int, input().split()))

    print((s[ri] - s[li - 1]))
def get_prime_list(n):
    l = [0 for _ in range(n)]
    i = 1
    while i < n:
        for j in range(2, int((i + 1) ** 0.5) + 1):
            if not (i + 1) % j:
                break
        else:
            l[i] = 1
        i += 1
    return l


n_max = 10**5
is_prime = get_prime_list(n_max)
is_2017 = [0 for _ in range(n_max)]
for i in range(2, n_max + 1):
    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:
        is_2017[i - 1] = 1
s = [0]
for i in range(n_max):
    s.append(s[i] + is_2017[i])
q = int(eval(input()))
for _ in range(q):
    li, ri = list(map(int, input().split()))
    print((s[ri] - s[li - 1]))

def erat(n):
    l = [0, 0] + [1 for _ in range(n - 1)]
    i = 2
    while i < n + 1:
        if l[i] == 1:
            for j in range(i**2, n + 1, i):
                l[j] = 0
        i += 1
    return l


n_max = 10**5
is_prime = erat(n_max)
is_2017 = [0 for _ in range(n_max + 1)]
for i in range(2, n_max + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        is_2017[i] = 1
s = [0]
for i in range(1, n_max + 1):
    s.append(s[i - 1] + is_2017[i])
q = int(eval(input()))
for _ in range(q):
    li, ri = list(map(int, input().split()))
    print((s[ri] - s[li - 1]))

-def get_prime_list(n): -    l = [0 for _ in range(n)] -    i = 1 -    while i < n: -        for j in range(2, int((i + 1) ** 0.5) + 1): -            if not (i + 1) % j: -                break -        else: -            l[i] = 1 +def erat(n): +    l = [0, 0] + [1 for _ in range(n - 1)] +    i = 2 +    while i < n + 1: +        if l[i] == 1: +            for j in range(i**2, n + 1, i): +                l[j] = 0 -is_prime = get_prime_list(n_max) -is_2017 = [0 for _ in range(n_max)] +is_prime = erat(n_max) +is_2017 = [0 for _ in range(n_max + 1)] -    if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]: -        is_2017[i - 1] = 1 +    if is_prime[i] and is_prime[(i + 1) // 2]: +        is_2017[i] = 1 -for i in range(n_max): -    s.append(s[i] + is_2017[i]) +for i in range(1, n_max + 1): +    s.append(s[i - 1] + is_2017[i])