def d_2017LikeNumber(Q, I):  # Q:クエリの数、I:探索区間の左端と右端

    def prime_list(M):

        # 0以上M以下の素数のリスト

        s = [True] * (M + 1)  # i番目の要素はiが素数ならTrue、非素数ならFalse

        s[0] = s[1] = False

        for x in range(2, int(M**0.5) + 1):

            if s[x]:

                for i in range(x + x, len(s), x):

                    # 素数xの倍数は素数ではない

                    s[i] = False

        return s



    def calc_like2017(M, p):

        # i番目の要素が、1以上i以下の"2017に似た数"の個数となるようなリスト

        # 0番目は0と定義する

        # M以下の素数のリストpを予め作っておく必要がある

        c = [0] * (M + 1)

        for i in range(3, M + 1, 2):  # 0,1,2は定義上2017に似た数にならない

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

                c[i] += 1

        for i in range(3, M + 1):

            c[i] += c[i - 1]

        return c



    c = calc_like2017(10**5, prime_list(10**5))

    ans = ''

    for query in I:

        l, r = query[0], query[1]

        ans += '{}\n'.format(c[r] - c[l - 1])

    return ans[:-1]



Q = int(eval(input()))

I = [[int(i) for i in input().split()] for j in range(Q)]

print((d_2017LikeNumber(Q, I)))
def d_2017_like_number():

    Q = int(eval(input()))

    I = [[int(i) for i in input().split()] for j in range(Q)]



    def prime_table(n):

        """n 以下の整数がそれぞれ素数かどうかのリスト (エラトステネスの篩)"""

        is_prime = [True] * (n + 1)

        is_prime[0] = is_prime[1] = False  # 0と1は素数でない

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

            if not is_prime[j]:

                continue

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

                is_prime[k] = False  # jの倍数は素数でない

        return is_prime



    def calc_like2017(m, p):

        # i 番目の要素が、1 以上 i 以下の "2017に似た数" の個数となるリストを返す

        # m 以下の素数のリスト p を予め作っておく必要がある

        c = [0] * (m + 1)  # 0番目は0と定義する

        for i in range(3, m + 1, 2):  # 0, 1, 2 は定義上2017に似た数にならない

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

                c[i] += 1

        for i in range(3, m + 1):

            c[i] += c[i - 1]

        return c



    like2017 = calc_like2017(10**5, prime_table(10**5))

    ans = [like2017[r] - like2017[l - 1] for l, r in I]

    return '\n'.join(map(str, ans))



print((d_2017_like_number()))
def d_2017LikeNumber(Q, I):  # Q:クエリの数、I:探索区間の左端と右端
    def prime_list(M):
        # 0以上M以下の素数のリスト
        s = [True] * (M + 1)  # i番目の要素はiが素数ならTrue、非素数ならFalse
        s[0] = s[1] = False
        for x in range(2, int(M**0.5) + 1):
            if s[x]:
                for i in range(x + x, len(s), x):
                    # 素数xの倍数は素数ではない
                    s[i] = False
        return s

    def calc_like2017(M, p):
        # i番目の要素が、1以上i以下の"2017に似た数"の個数となるようなリスト
        # 0番目は0と定義する
        # M以下の素数のリストpを予め作っておく必要がある
        c = [0] * (M + 1)
        for i in range(3, M + 1, 2):  # 0,1,2は定義上2017に似た数にならない
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, M + 1):
            c[i] += c[i - 1]
        return c

    c = calc_like2017(10**5, prime_list(10**5))
    ans = ""
    for query in I:
        l, r = query[0], query[1]
        ans += "{}\n".format(c[r] - c[l - 1])
    return ans[:-1]


Q = int(eval(input()))
I = [[int(i) for i in input().split()] for j in range(Q)]
print((d_2017LikeNumber(Q, I)))

def d_2017_like_number():
    Q = int(eval(input()))
    I = [[int(i) for i in input().split()] for j in range(Q)]

    def prime_table(n):
        """n 以下の整数がそれぞれ素数かどうかのリスト (エラトステネスの篩)"""
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False  # 0と1は素数でない
        for j in range(2, int(n**0.5) + 1):
            if not is_prime[j]:
                continue
            for k in range(j * 2, n + 1, j):
                is_prime[k] = False  # jの倍数は素数でない
        return is_prime

    def calc_like2017(m, p):
        # i 番目の要素が、1 以上 i 以下の "2017に似た数" の個数となるリストを返す
        # m 以下の素数のリスト p を予め作っておく必要がある
        c = [0] * (m + 1)  # 0番目は0と定義する
        for i in range(3, m + 1, 2):  # 0, 1, 2 は定義上2017に似た数にならない
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, m + 1):
            c[i] += c[i - 1]
        return c

    like2017 = calc_like2017(10**5, prime_table(10**5))
    ans = [like2017[r] - like2017[l - 1] for l, r in I]
    return "\n".join(map(str, ans))


print((d_2017_like_number()))

-def d_2017LikeNumber(Q, I):  # Q:クエリの数、I:探索区間の左端と右端 -    def prime_list(M): -        # 0以上M以下の素数のリスト -        s = [True] * (M + 1)  # i番目の要素はiが素数ならTrue、非素数ならFalse -        s[0] = s[1] = False -        for x in range(2, int(M**0.5) + 1): -            if s[x]: -                for i in range(x + x, len(s), x): -                    # 素数xの倍数は素数ではない -                    s[i] = False -        return s +def d_2017_like_number(): +    Q = int(eval(input())) +    I = [[int(i) for i in input().split()] for j in range(Q)] -    def calc_like2017(M, p): -        # i番目の要素が、1以上i以下の"2017に似た数"の個数となるようなリスト -        # 0番目は0と定義する -        # M以下の素数のリストpを予め作っておく必要がある -        c = [0] * (M + 1) -        for i in range(3, M + 1, 2):  # 0,1,2は定義上2017に似た数にならない +    def prime_table(n): +        """n 以下の整数がそれぞれ素数かどうかのリスト (エラトステネスの篩)""" +        is_prime = [True] * (n + 1) +        is_prime[0] = is_prime[1] = False  # 0と1は素数でない +        for j in range(2, int(n**0.5) + 1): +            if not is_prime[j]: +                continue +            for k in range(j * 2, n + 1, j): +                is_prime[k] = False  # jの倍数は素数でない +        return is_prime + +    def calc_like2017(m, p): +        # i 番目の要素が、1 以上 i 以下の "2017に似た数" の個数となるリストを返す +        # m 以下の素数のリスト p を予め作っておく必要がある +        c = [0] * (m + 1)  # 0番目は0と定義する +        for i in range(3, m + 1, 2):  # 0, 1, 2 は定義上2017に似た数にならない -        for i in range(3, M + 1): +        for i in range(3, m + 1): -    c = calc_like2017(10**5, prime_list(10**5)) -    ans = "" -    for query in I: -        l, r = query[0], query[1] -        ans += "{}\n".format(c[r] - c[l - 1]) -    return ans[:-1] +    like2017 = calc_like2017(10**5, prime_table(10**5)) +    ans = [like2017[r] - like2017[l - 1] for l, r in I] +    return "\n".join(map(str, ans)) -Q = int(eval(input())) -I = [[int(i) for i in input().split()] for j in range(Q)] -print((d_2017LikeNumber(Q, I))) +print((d_2017_like_number()))