def solve():

    q = int(eval(input()))

    l, r = [], []

    for _ in range(q):

        tmp_l, tmp_r = list(map(int, input().split(" ")))

        l.append(tmp_l)

        r.append(tmp_r)



    p = [True for i in range(100000)]

    p[0] = p[1] = False

    for i in range(2, 100000):

        if p[i]:

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

                p[j] = False



    s = [0 for i in range(100000)]

    for i in range(1, 100000, 2):

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

            s[i] = 1



    for i in range(100000 - 1):

        s[i + 1] += s[i]



    for i in range(q):

        print((s[r[i]] - s[l[i] - 1]))





solve()
def prime_TorF(n):

    p = [True for i in range(n)]

    p[0] = p[1] = False

    for i in range(2, 100000):

        if p[i]:

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

                p[j] = False



    return p





def solve():

    q = int(eval(input()))

    l, r = [], []

    for _ in range(q):

        tmp_l, tmp_r = list(map(int, input().split(" ")))

        l.append(tmp_l)

        r.append(tmp_r)



    p = prime_TorF(100000)



    s = [0 for i in range(100000)]

    for i in range(1, 100000, 2):

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

            s[i] = 1



    for i in range(100000 - 1):

        s[i + 1] += s[i]



    for i in range(q):

        print((s[r[i]] - s[l[i] - 1]))





solve()
def solve():
    q = int(eval(input()))
    l, r = [], []
    for _ in range(q):
        tmp_l, tmp_r = list(map(int, input().split(" ")))
        l.append(tmp_l)
        r.append(tmp_r)
    p = [True for i in range(100000)]
    p[0] = p[1] = False
    for i in range(2, 100000):
        if p[i]:
            for j in range(2 * i, 100000, i):
                p[j] = False
    s = [0 for i in range(100000)]
    for i in range(1, 100000, 2):
        if p[i] and p[(i + 1) // 2]:
            s[i] = 1
    for i in range(100000 - 1):
        s[i + 1] += s[i]
    for i in range(q):
        print((s[r[i]] - s[l[i] - 1]))


solve()

def prime_TorF(n):
    p = [True for i in range(n)]
    p[0] = p[1] = False
    for i in range(2, 100000):
        if p[i]:
            for j in range(2 * i, 100000, i):
                p[j] = False
    return p


def solve():
    q = int(eval(input()))
    l, r = [], []
    for _ in range(q):
        tmp_l, tmp_r = list(map(int, input().split(" ")))
        l.append(tmp_l)
        r.append(tmp_r)
    p = prime_TorF(100000)
    s = [0 for i in range(100000)]
    for i in range(1, 100000, 2):
        if p[i] and p[(i + 1) // 2]:
            s[i] = 1
    for i in range(100000 - 1):
        s[i + 1] += s[i]
    for i in range(q):
        print((s[r[i]] - s[l[i] - 1]))


solve()

+def prime_TorF(n): +    p = [True for i in range(n)] +    p[0] = p[1] = False +    for i in range(2, 100000): +        if p[i]: +            for j in range(2 * i, 100000, i): +                p[j] = False +    return p + + -    p = [True for i in range(100000)] -    p[0] = p[1] = False -    for i in range(2, 100000): -        if p[i]: -            for j in range(2 * i, 100000, i): -                p[j] = False +    p = prime_TorF(100000)