#!/usr/bin/env python3

# coding=utf-8



import sys



import numpy as np



num_max = 100000

primes = np.asarray([True for _ in range(num_max + 1)])

for i in range(num_max + 1):

    if i == 0 or i == 1:

        primes[i] = False

    else:

        primes[i * 2::i] = False

primes = set(np.arange(num_max + 1)[primes])

like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]

cumsum = np.cumsum(like2017)



q = int(sys.stdin.readline().strip())

for _ in range(q):

    l, r = sys.stdin.readline().strip().split(" ")

    l = int(l)

    r = int(r)

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

#!/usr/bin/env python3

# coding=utf-8



import sys



import numpy as np



num_max = 100000

primes = np.asarray([True for _ in range(num_max + 1)])

for i in range(num_max + 1):

    if i == 0 or i == 1:

        primes[i] = False

    elif primes[i]:

        primes[i * 2::i] = False

primes = set(np.arange(num_max + 1)[primes])

like2017 = [1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)]

cumsum = np.cumsum(like2017)



q = int(sys.stdin.readline().strip())

for _ in range(q):

    l, r = sys.stdin.readline().strip().split(" ")

    l = int(l)

    r = int(r)

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

#!/usr/bin/env python3
# coding=utf-8
import sys
import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    else:
        primes[i * 2 :: i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [
    1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)
]
cumsum = np.cumsum(like2017)
q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print((cumsum[r] - cumsum[l - 1]))

#!/usr/bin/env python3
# coding=utf-8
import sys
import numpy as np

num_max = 100000
primes = np.asarray([True for _ in range(num_max + 1)])
for i in range(num_max + 1):
    if i == 0 or i == 1:
        primes[i] = False
    elif primes[i]:
        primes[i * 2 :: i] = False
primes = set(np.arange(num_max + 1)[primes])
like2017 = [
    1 if i in primes and (i + 1) // 2 in primes else 0 for i in range(num_max + 1)
]
cumsum = np.cumsum(like2017)
q = int(sys.stdin.readline().strip())
for _ in range(q):
    l, r = sys.stdin.readline().strip().split(" ")
    l = int(l)
    r = int(r)
    print((cumsum[r] - cumsum[l - 1]))

-    else: +    elif primes[i]: