import sys

sys.setrecursionlimit(2147483647)

INF=float("inf")

MOD=10**9+7

input=lambda :sys.stdin.readline().rstrip()

def resolve():

    def prime(n):

        if n<=1: return False

        A = [i for i in range(2, n+1)]

        P = []

        lim = n**.5

        while True:

            prime = A[0]

            if prime > lim: break

            P.append(prime)

            i = 0

            while i < len(A):

                if A[i] % prime == 0:

                    A.pop(i)

                    continue

                i += 1

        for a in A:

            P.append(a)

        return P



    C=5+10**5

    S=[0]*C

    T=[0]*C

    for p in prime(C):

        S[p]=1

    for i in range(C):

        if i%2==0: continue

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

            T[i]=1

    # cumsum

    for i in range(C-1):

        T[i+1]+=T[i]

    # input

    q=int(eval(input()))

    for _ in range(q):

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

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

resolve()
import sys

sys.setrecursionlimit(2147483647)

INF=float("inf")

MOD=10**9+7

input=lambda :sys.stdin.readline().rstrip()

def resolve():

    c=10**5+1

    # S[i]: iがprimeかを指すboolean

    S=[1]*c

    S[0]=0; S[1]=0

    for i in range(2,c):

        if S[i]==0: continue

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

            S[j]=0

    # T[i]: iが2017-like primeかを指すboolean

    T=[0]*c

    for i in range(3,c,2):

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

            T[i]=1

    # cumsum

    for i in range(c-1):

        T[i+1]+=T[i]

    # input

    q=int(eval(input()))

    for _ in range(q):

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

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

resolve()
import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7
input = lambda: sys.stdin.readline().rstrip()


def resolve():
    def prime(n):
        if n <= 1:
            return False
        A = [i for i in range(2, n + 1)]
        P = []
        lim = n**0.5
        while True:
            prime = A[0]
            if prime > lim:
                break
            P.append(prime)
            i = 0
            while i < len(A):
                if A[i] % prime == 0:
                    A.pop(i)
                    continue
                i += 1
        for a in A:
            P.append(a)
        return P

    C = 5 + 10**5
    S = [0] * C
    T = [0] * C
    for p in prime(C):
        S[p] = 1
    for i in range(C):
        if i % 2 == 0:
            continue
        if S[i] == 1 and S[(i + 1) // 2] == 1:
            T[i] = 1
    # cumsum
    for i in range(C - 1):
        T[i + 1] += T[i]
    # input
    q = int(eval(input()))
    for _ in range(q):
        l, r = list(map(int, input().split()))
        print((T[r] - T[l - 1]))


resolve()

import sys

sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7
input = lambda: sys.stdin.readline().rstrip()


def resolve():
    c = 10**5 + 1
    # S[i]: iがprimeかを指すboolean
    S = [1] * c
    S[0] = 0
    S[1] = 0
    for i in range(2, c):
        if S[i] == 0:
            continue
        for j in range(2 * i, c, i):
            S[j] = 0
    # T[i]: iが2017-like primeかを指すboolean
    T = [0] * c
    for i in range(3, c, 2):
        if S[i] and S[(i + 1) // 2]:
            T[i] = 1
    # cumsum
    for i in range(c - 1):
        T[i + 1] += T[i]
    # input
    q = int(eval(input()))
    for _ in range(q):
        l, r = list(map(int, input().split()))
        print((T[r] - T[l - 1]))


resolve()

-    def prime(n): -        if n <= 1: -            return False -        A = [i for i in range(2, n + 1)] -        P = [] -        lim = n**0.5 -        while True: -            prime = A[0] -            if prime > lim: -                break -            P.append(prime) -            i = 0 -            while i < len(A): -                if A[i] % prime == 0: -                    A.pop(i) -                    continue -                i += 1 -        for a in A: -            P.append(a) -        return P - -    C = 5 + 10**5 -    S = [0] * C -    T = [0] * C -    for p in prime(C): -        S[p] = 1 -    for i in range(C): -        if i % 2 == 0: +    c = 10**5 + 1 +    # S[i]: iがprimeかを指すboolean +    S = [1] * c +    S[0] = 0 +    S[1] = 0 +    for i in range(2, c): +        if S[i] == 0: -        if S[i] == 1 and S[(i + 1) // 2] == 1: +        for j in range(2 * i, c, i): +            S[j] = 0 +    # T[i]: iが2017-like primeかを指すboolean +    T = [0] * c +    for i in range(3, c, 2): +        if S[i] and S[(i + 1) // 2]: -    for i in range(C - 1): +    for i in range(c - 1):