#!/usr/bin/env python3

from itertools import accumulate

def erat(m):

    p = [1] * m

    p[0] = p[1] = 0

    for x in range(2, int((~-m)**.5) + 1):

        if p[x]:

            for y in range(x*x, m, x):

                p[y] = 0

    return p



INF = 10**5 + 1

p = erat(INF)

q = [0] * INF

for n in range(INF):

    q[n] = n%2 * p[n] * p[-~n//2]

*a, = accumulate([0] + q)

for _ in [None] * int(eval(input())):

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

    print((a[r + 1] - a[l]))
def erat(M):

    p = [1] * M

    p[0] = p[1] = 0

    for x in range(2, int((M - 1)**.5) + 1):

        if p[x]:

            for y in range(x*x, M, x):

                p[y] = 0

    return p

INF = 10**5 + 1

p = erat(INF)

q = [0] * INF

from itertools import*

for i in range(INF):

    q[i] = i%2 * p[i] * p[-~i//2]

*a, = accumulate([0] + q)

for _ in [None] * int(eval(input())):

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

    print((a[-~r] - a[l]))

#!/usr/bin/env python3
from itertools import accumulate


def erat(m):
    p = [1] * m
    p[0] = p[1] = 0
    for x in range(2, int((~-m) ** 0.5) + 1):
        if p[x]:
            for y in range(x * x, m, x):
                p[y] = 0
    return p


INF = 10**5 + 1
p = erat(INF)
q = [0] * INF
for n in range(INF):
    q[n] = n % 2 * p[n] * p[-~n // 2]
(*a,) = accumulate([0] + q)
for _ in [None] * int(eval(input())):
    l, r = list(map(int, input().split()))
    print((a[r + 1] - a[l]))

def erat(M):
    p = [1] * M
    p[0] = p[1] = 0
    for x in range(2, int((M - 1) ** 0.5) + 1):
        if p[x]:
            for y in range(x * x, M, x):
                p[y] = 0
    return p


INF = 10**5 + 1
p = erat(INF)
q = [0] * INF
from itertools import *

for i in range(INF):
    q[i] = i % 2 * p[i] * p[-~i // 2]
(*a,) = accumulate([0] + q)
for _ in [None] * int(eval(input())):
    l, r = list(map(int, input().split()))
    print((a[-~r] - a[l]))

-#!/usr/bin/env python3 -from itertools import accumulate - - -def erat(m): -    p = [1] * m +def erat(M): +    p = [1] * M -    for x in range(2, int((~-m) ** 0.5) + 1): +    for x in range(2, int((M - 1) ** 0.5) + 1): -            for y in range(x * x, m, x): +            for y in range(x * x, M, x): -for n in range(INF): -    q[n] = n % 2 * p[n] * p[-~n // 2] +from itertools import * + +for i in range(INF): +    q[i] = i % 2 * p[i] * p[-~i // 2] -    print((a[r + 1] - a[l])) +    print((a[-~r] - a[l]))