'''

https://atcoder.jp/contests/abc084/tasks/abc084_d

'''

def main():

    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10000000)

    from collections import Counter, deque

    #from collections import defaultdict

    from itertools import combinations, permutations

    #from itertools import accumulate, product

    from bisect import bisect_left,bisect_right

    import heapq

    from math import floor, ceil

    #from operator import itemgetter



    #inf = 10**17

    #mod = 1000000007



    def primecheck(n):

        p = [True] * (n + 1)

        p[0] = False

        p[1] = False

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

            if p[i]:

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

                    p[j] = False

        return p

    

    p = primecheck(10**5)

    cnt = 0

    res = [0]*(10**5)

    for i in range(10**5):

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

            cnt += 1

        res[i] = cnt





    q = int(eval(input()))

    for _ in range(q):

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

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



if __name__ == '__main__':

    main()
'''

https://atcoder.jp/contests/abc084/tasks/abc084_d

'''

def main():

    import sys

    input = sys.stdin.readline

    sys.setrecursionlimit(10000000)

    from collections import Counter, deque

    #from collections import defaultdict

    from itertools import combinations, permutations

    #from itertools import accumulate, product

    from bisect import bisect_left,bisect_right

    import heapq

    from math import floor, ceil

    #from operator import itemgetter



    #inf = 10**17

    #mod = 1000000007



    def primecheck(n):

        p = [True] * (n + 1)

        p[0] = False

        p[1] = False

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

            if p[i]:

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

                    p[j] = False

        return p

    

    p = primecheck(10**5)

    cnt = 0

    res = [0]*(10**5)

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

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

            cnt += 1

        res[i] = cnt





    q = int(eval(input()))

    for _ in range(q):

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

        if l==1:

            print((res[r]))

        elif res[l]==res[l-2]:

            print((res[r]-res[l]))

        else:

            print((res[r]-res[l]+1))



if __name__ == '__main__':

    main()
"""
https://atcoder.jp/contests/abc084/tasks/abc084_d
"""


def main():
    import sys

    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque

    # from collections import defaultdict
    from itertools import combinations, permutations

    # from itertools import accumulate, product
    from bisect import bisect_left, bisect_right
    import heapq
    from math import floor, ceil

    # from operator import itemgetter
    # inf = 10**17
    # mod = 1000000007
    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n**0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p

    p = primecheck(10**5)
    cnt = 0
    res = [0] * (10**5)
    for i in range(10**5):
        if p[i] == p[(i + 1) // 2] == 1:
            cnt += 1
        res[i] = cnt
    q = int(eval(input()))
    for _ in range(q):
        l, r = list(map(int, input().split()))
        print((res[r] - res[l - 1]))


if __name__ == "__main__":
    main()

"""
https://atcoder.jp/contests/abc084/tasks/abc084_d
"""


def main():
    import sys

    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque

    # from collections import defaultdict
    from itertools import combinations, permutations

    # from itertools import accumulate, product
    from bisect import bisect_left, bisect_right
    import heapq
    from math import floor, ceil

    # from operator import itemgetter
    # inf = 10**17
    # mod = 1000000007
    def primecheck(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(2, int(n**0.5) + 1):
            if p[i]:
                for j in range(i * i, n + 1, i):
                    p[j] = False
        return p

    p = primecheck(10**5)
    cnt = 0
    res = [0] * (10**5)
    for i in range(1, 10**5, 2):
        if p[i] == p[(i + 1) // 2] == 1:
            cnt += 1
        res[i] = cnt
    q = int(eval(input()))
    for _ in range(q):
        l, r = list(map(int, input().split()))
        if l == 1:
            print((res[r]))
        elif res[l] == res[l - 2]:
            print((res[r] - res[l]))
        else:
            print((res[r] - res[l] + 1))


if __name__ == "__main__":
    main()

-    for i in range(10**5): +    for i in range(1, 10**5, 2): -        print((res[r] - res[l - 1])) +        if l == 1: +            print((res[r])) +        elif res[l] == res[l - 2]: +            print((res[r] - res[l])) +        else: +            print((res[r] - res[l] + 1))