def slove():

    import sys

    input = sys.stdin.readline

    pl = {}

    p = [True] * (10 ** 5 + 1)

    p[0] = False

    p[1] = False

    cnt = 0

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

    for i in range(2, len(p)):

        if p[i]:

            pl[i] = 1

            for j in range(i, len(p), i):

                p[j] = False

        if i % 2 != 0:

            if (i + 1) // 2 in pl and i in pl:

                cnt += 1

        pll[i] = cnt

    q = int(input().rstrip('\n'))

    lr = [list(map(int, input().rstrip('\n').split())) for _ in range(q)]

    for l, r in lr:

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





if __name__ == '__main__':

    slove()

def slove():

    import sys

    input = sys.stdin.readline

    pb = [True] * (10 ** 5 + 1)

    pb[0] = False

    pb[1] = False

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

    pc = 0

    for i in range(2, len(pb)):

        if pb[i]:

            for j in range(i + i, len(pb), i):

                if pb[j]:

                    pb[j] = False

            if pb[(i + 1) // 2]:

                pc += 1

        pl[i] = pc

    n = int(input().rstrip('\n'))

    for i in range(n):

        l, r = list(map(int, input().rstrip('\n').split()))

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





if __name__ == '__main__':

    slove()

def slove():
    import sys

    input = sys.stdin.readline
    pl = {}
    p = [True] * (10**5 + 1)
    p[0] = False
    p[1] = False
    cnt = 0
    pll = [0] * (10**5 + 1)
    for i in range(2, len(p)):
        if p[i]:
            pl[i] = 1
            for j in range(i, len(p), i):
                p[j] = False
        if i % 2 != 0:
            if (i + 1) // 2 in pl and i in pl:
                cnt += 1
        pll[i] = cnt
    q = int(input().rstrip("\n"))
    lr = [list(map(int, input().rstrip("\n").split())) for _ in range(q)]
    for l, r in lr:
        print((pll[r] - pll[l - 1]))


if __name__ == "__main__":
    slove()

def slove():
    import sys

    input = sys.stdin.readline
    pb = [True] * (10**5 + 1)
    pb[0] = False
    pb[1] = False
    pl = [0] * (10**5 + 1)
    pc = 0
    for i in range(2, len(pb)):
        if pb[i]:
            for j in range(i + i, len(pb), i):
                if pb[j]:
                    pb[j] = False
            if pb[(i + 1) // 2]:
                pc += 1
        pl[i] = pc
    n = int(input().rstrip("\n"))
    for i in range(n):
        l, r = list(map(int, input().rstrip("\n").split()))
        print((pl[r] - pl[l - 1]))


if __name__ == "__main__":
    slove()

-    pl = {} -    p = [True] * (10**5 + 1) -    p[0] = False -    p[1] = False -    cnt = 0 -    pll = [0] * (10**5 + 1) -    for i in range(2, len(p)): -        if p[i]: -            pl[i] = 1 -            for j in range(i, len(p), i): -                p[j] = False -        if i % 2 != 0: -            if (i + 1) // 2 in pl and i in pl: -                cnt += 1 -        pll[i] = cnt -    q = int(input().rstrip("\n")) -    lr = [list(map(int, input().rstrip("\n").split())) for _ in range(q)] -    for l, r in lr: -        print((pll[r] - pll[l - 1])) +    pb = [True] * (10**5 + 1) +    pb[0] = False +    pb[1] = False +    pl = [0] * (10**5 + 1) +    pc = 0 +    for i in range(2, len(pb)): +        if pb[i]: +            for j in range(i + i, len(pb), i): +                if pb[j]: +                    pb[j] = False +            if pb[(i + 1) // 2]: +                pc += 1 +        pl[i] = pc +    n = int(input().rstrip("\n")) +    for i in range(n): +        l, r = list(map(int, input().rstrip("\n").split())) +        print((pl[r] - pl[l - 1]))