class BIT():

	def __init__(self, N):

		self.bit = [0] * (N + 1)

		self.N = N



	def add(self, a, w):

		x = a

		while x <= self.N:

			self.bit[x] += w

			x += x & (- x)



	def sum(self, a):

		ret = 0

		x = a

		while x > 0:

			ret += self.bit[x]

			x -= x & (- x)

		return ret





MAX_N = 10 ** 5

SQRT_MN = 318

isp = [1] * (MAX_N + 1)

p_list = []

isp[0] = isp[1] = 0

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

	if isp[i] == 0:

		continue

	p_list.append(i)

	for prod in range(2, MAX_N // i + 1):

		isp[i * prod] = 0



bit = BIT(MAX_N)

for p in range(3, MAX_N + 1):

	if isp[p] and isp[(p + 1) // 2]:

		bit.add(p, 1)



Q = int(eval(input()))

for i in range(Q):

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

	print((bit.sum(r) - bit.sum(l - 1)))

MAX_N = 10 ** 5

SQRT_MN = 318

isp = [1] * (MAX_N + 1)

p_list = []

isp[0] = isp[1] = 0

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

	if isp[i] == 0:

		continue

	p_list.append(i)

	for prod in range(2, MAX_N // i + 1):

		isp[i * prod] = 0



like_num = [0] * (MAX_N + 1)

for p in range(3, MAX_N + 1):

	if isp[p] and isp[(p + 1) // 2]:

		like_num[p] = 1

	like_num[p] += like_num[p - 1]



Q = int(eval(input()))

for i in range(Q):

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

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

class BIT:
    def __init__(self, N):
        self.bit = [0] * (N + 1)
        self.N = N

    def add(self, a, w):
        x = a
        while x <= self.N:
            self.bit[x] += w
            x += x & (-x)

    def sum(self, a):
        ret = 0
        x = a
        while x > 0:
            ret += self.bit[x]
            x -= x & (-x)
        return ret


MAX_N = 10**5
SQRT_MN = 318
isp = [1] * (MAX_N + 1)
p_list = []
isp[0] = isp[1] = 0
for i in range(2, SQRT_MN + 1):
    if isp[i] == 0:
        continue
    p_list.append(i)
    for prod in range(2, MAX_N // i + 1):
        isp[i * prod] = 0
bit = BIT(MAX_N)
for p in range(3, MAX_N + 1):
    if isp[p] and isp[(p + 1) // 2]:
        bit.add(p, 1)
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((bit.sum(r) - bit.sum(l - 1)))

MAX_N = 10**5
SQRT_MN = 318
isp = [1] * (MAX_N + 1)
p_list = []
isp[0] = isp[1] = 0
for i in range(2, SQRT_MN + 1):
    if isp[i] == 0:
        continue
    p_list.append(i)
    for prod in range(2, MAX_N // i + 1):
        isp[i * prod] = 0
like_num = [0] * (MAX_N + 1)
for p in range(3, MAX_N + 1):
    if isp[p] and isp[(p + 1) // 2]:
        like_num[p] = 1
    like_num[p] += like_num[p - 1]
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((like_num[r] - like_num[l - 1]))

-class BIT: -    def __init__(self, N): -        self.bit = [0] * (N + 1) -        self.N = N - -    def add(self, a, w): -        x = a -        while x <= self.N: -            self.bit[x] += w -            x += x & (-x) - -    def sum(self, a): -        ret = 0 -        x = a -        while x > 0: -            ret += self.bit[x] -            x -= x & (-x) -        return ret - - -bit = BIT(MAX_N) +like_num = [0] * (MAX_N + 1) -        bit.add(p, 1) +        like_num[p] = 1 +    like_num[p] += like_num[p - 1] -    print((bit.sum(r) - bit.sum(l - 1))) +    print((like_num[r] - like_num[l - 1]))