def prime_table(m):

    t = [True] * (m + 1)

    i = 2

    while i * i <= m:

        if t[i]:

            j = i + i

            while j <= m:

                t[j] = False

                j += i

        i += 1

    return t

    # t[i] = i が素数ならTrue





Q = int(eval(input()))

pt = prime_table(10 ** 5)

sn = [False] * (10 ** 5 + 1)

for i in range(3, 10 ** 5, 2):

    sn[i] = pt[i] and pt[(i + 1) // 2]

c = [0] * (10 ** 5 + 1)

for i in range(3, 10 ** 5, 2):

    c[i] = c[i - 2] + (1 if sn[i] else 0)

    # print(i, c[i])

for _ in range(Q):

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

    print((c[r] - c[l - 2]))
class Sieve:

    """区間[2,n]の値を素因数分解する"""



    def __init__(self, n=1):

        primes = []

        f = [0] * (n + 1)

        f[0] = f[1] = -1

        for i in range(2, n + 1):  # 素数を探す

            if f[i]: continue

            primes.append(i)

            f[i] = i  # 素数には自身を代入

            for j in range(i * i, n + 1, i):  # 合成数に素因数を書き込む

                if not f[j]:

                    f[j] = i  # 最小の素因数を代入

        self.primes = primes

        self.f = f



    # def is_prime(self, x) -> bool:  # 素数判定

    #     return self.f[x] == x

    #

    # def factor_list(self, x) -> list:  # 素因数分解の昇順リスト, [2,2,3,5,...]

    #     res = []

    #     while x != 1:

    #         res.append(self.f[x])

    #         x //= self.f[x]

    #     return res

    #

    # def factor(self, x) -> list:  # 素因数分解の頻度リスト, [[2,x],[3,y],[5,z],...]

    #     fl = self.factor_list(x)

    #     if not fl: return []

    #     res = [[fl[0], 0]]

    #     for p in fl:

    #         if res[-1][0] == p:

    #             res[-1][1] += 1

    #         else:

    #             res.append([p, 1])

    #     return res





def main():

    import sys



    input = sys.stdin.readline



    sieve = Sieve(10 ** 5)

    prime_set = set(sieve.primes)



    acc = [0] * (10 ** 5 + 1)

    cnt = 0

    for x in range(1, 10 ** 5 + 1):

        if (x % 2 == 1) and (x in prime_set) and ((x + 1) // 2 in prime_set):

            cnt += 1

        acc[x] = cnt



    q = int(eval(input()))

    for _ in range(q):

        left, right = list(map(int, input().split()))  # [left,right]<=10**5

        res = acc[right] - acc[left - 1]

        print(res)





if __name__ == '__main__':

    main()

def prime_table(m):
    t = [True] * (m + 1)
    i = 2
    while i * i <= m:
        if t[i]:
            j = i + i
            while j <= m:
                t[j] = False
                j += i
        i += 1
    return t
    # t[i] = i が素数ならTrue


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

class Sieve:
    """区間[2,n]の値を素因数分解する"""

    def __init__(self, n=1):
        primes = []
        f = [0] * (n + 1)
        f[0] = f[1] = -1
        for i in range(2, n + 1):  # 素数を探す
            if f[i]:
                continue
            primes.append(i)
            f[i] = i  # 素数には自身を代入
            for j in range(i * i, n + 1, i):  # 合成数に素因数を書き込む
                if not f[j]:
                    f[j] = i  # 最小の素因数を代入
        self.primes = primes
        self.f = f

    # def is_prime(self, x) -> bool:  # 素数判定
    #     return self.f[x] == x
    #
    # def factor_list(self, x) -> list:  # 素因数分解の昇順リスト, [2,2,3,5,...]
    #     res = []
    #     while x != 1:
    #         res.append(self.f[x])
    #         x //= self.f[x]
    #     return res
    #
    # def factor(self, x) -> list:  # 素因数分解の頻度リスト, [[2,x],[3,y],[5,z],...]
    #     fl = self.factor_list(x)
    #     if not fl: return []
    #     res = [[fl[0], 0]]
    #     for p in fl:
    #         if res[-1][0] == p:
    #             res[-1][1] += 1
    #         else:
    #             res.append([p, 1])
    #     return res


def main():
    import sys

    input = sys.stdin.readline
    sieve = Sieve(10**5)
    prime_set = set(sieve.primes)
    acc = [0] * (10**5 + 1)
    cnt = 0
    for x in range(1, 10**5 + 1):
        if (x % 2 == 1) and (x in prime_set) and ((x + 1) // 2 in prime_set):
            cnt += 1
        acc[x] = cnt
    q = int(eval(input()))
    for _ in range(q):
        left, right = list(map(int, input().split()))  # [left,right]<=10**5
        res = acc[right] - acc[left - 1]
        print(res)


if __name__ == "__main__":
    main()

-def prime_table(m): -    t = [True] * (m + 1) -    i = 2 -    while i * i <= m: -        if t[i]: -            j = i + i -            while j <= m: -                t[j] = False -                j += i -        i += 1 -    return t -    # t[i] = i が素数ならTrue +class Sieve: +    """区間[2,n]の値を素因数分解する""" + +    def __init__(self, n=1): +        primes = [] +        f = [0] * (n + 1) +        f[0] = f[1] = -1 +        for i in range(2, n + 1):  # 素数を探す +            if f[i]: +                continue +            primes.append(i) +            f[i] = i  # 素数には自身を代入 +            for j in range(i * i, n + 1, i):  # 合成数に素因数を書き込む +                if not f[j]: +                    f[j] = i  # 最小の素因数を代入 +        self.primes = primes +        self.f = f + +    # def is_prime(self, x) -> bool:  # 素数判定 +    #     return self.f[x] == x +    # +    # def factor_list(self, x) -> list:  # 素因数分解の昇順リスト, [2,2,3,5,...] +    #     res = [] +    #     while x != 1: +    #         res.append(self.f[x]) +    #         x //= self.f[x] +    #     return res +    # +    # def factor(self, x) -> list:  # 素因数分解の頻度リスト, [[2,x],[3,y],[5,z],...] +    #     fl = self.factor_list(x) +    #     if not fl: return [] +    #     res = [[fl[0], 0]] +    #     for p in fl: +    #         if res[-1][0] == p: +    #             res[-1][1] += 1 +    #         else: +    #             res.append([p, 1]) +    #     return res -Q = int(eval(input())) -pt = prime_table(10**5) -sn = [False] * (10**5 + 1) -for i in range(3, 10**5, 2): -    sn[i] = pt[i] and pt[(i + 1) // 2] -c = [0] * (10**5 + 1) -for i in range(3, 10**5, 2): -    c[i] = c[i - 2] + (1 if sn[i] else 0) -    # print(i, c[i]) -for _ in range(Q): -    l, r = list(map(int, input().split())) -    print((c[r] - c[l - 2])) +def main(): +    import sys + +    input = sys.stdin.readline +    sieve = Sieve(10**5) +    prime_set = set(sieve.primes) +    acc = [0] * (10**5 + 1) +    cnt = 0 +    for x in range(1, 10**5 + 1): +        if (x % 2 == 1) and (x in prime_set) and ((x + 1) // 2 in prime_set): +            cnt += 1 +        acc[x] = cnt +    q = int(eval(input())) +    for _ in range(q): +        left, right = list(map(int, input().split()))  # [left,right]<=10**5 +        res = acc[right] - acc[left - 1] +        print(res) + + +if __name__ == "__main__": +    main()