import bisect

a = [True] * 100001

a[0] = False

a[1] = False

p = []

for i in range(2, 100001):

    if a[i]:

        for j in range(i * 2, 100001, i):

            if a[j]:

                a[j] = False

        if i % 2 != 0 and a[(i + 1) // 2]:

            p.append(i)

q = int(eval(input()))

for i in range(q):

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

    print((bisect.bisect_right(p, r) - bisect.bisect_left(p, l)))

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()

import bisect

a = [True] * 100001
a[0] = False
a[1] = False
p = []
for i in range(2, 100001):
    if a[i]:
        for j in range(i * 2, 100001, i):
            if a[j]:
                a[j] = False
        if i % 2 != 0 and a[(i + 1) // 2]:
            p.append(i)
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((bisect.bisect_right(p, r) - bisect.bisect_left(p, l)))

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()

-import bisect +def slove(): +    import sys -a = [True] * 100001 -a[0] = False -a[1] = False -p = [] -for i in range(2, 100001): -    if a[i]: -        for j in range(i * 2, 100001, i): -            if a[j]: -                a[j] = False -        if i % 2 != 0 and a[(i + 1) // 2]: -            p.append(i) -q = int(eval(input())) -for i in range(q): -    l, r = list(map(int, input().split())) -    print((bisect.bisect_right(p, r) - bisect.bisect_left(p, l))) +    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()