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

prime[0]=False

prime[1]=False

for i in range(2,10**3):

  if i*i>10**5:

    break

  if prime[i]:

    for j in range(i,10**5):

      if i*j>10**5:

        break

      prime[i*j]=False



prime2017 = [x for x in prime]

prime2017[2] = False

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

  if prime[i]:

    prime2017[i] = prime[(i+1)//2]



count = 0

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

for i in range((10**5)+1):

  if prime2017[i]:

    count+=1

  csum[i]=count



N = int(eval(input()))

for _ in range(N):

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

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

    
import sys

import heapq

import bisect



mod = 10**9+7

dd = ((-1,0),(1,0),(0,-1),(0,1))



def I(): return(int(sys.stdin.readline()))

def LI(): return([int(x) for x in sys.stdin.readline().split()])

def S(): return(sys.stdin.readline()[:-1])

def IR(n): return([I() for _ in range(n)])



def GCD(a,b):

    while b!=0:

        a,b = b,a%b

    return a



def LCM(a,b):

    return a * b // GCD(a,b)



def Eratosthenes(N):

    r = [True]*(N+1)

    r[0] = False

    r[1] = False

    i = 2

    while i*i<=N:

        if r[i]: 

            j = i

            while i*j<=N:

                r[i*j]=False

                j+=1

        i+=1

    return(r)



def main():

    prime = Eratosthenes(10**5)

    prime_2017 = [False]*(10**5+1)

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

        if prime[i]:

            prime_2017[i] = prime[(i+1)//2]



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

    nxt = 0



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

        if prime_2017[i]:

            nxt += 1

        cnt[i] = nxt



    Q = I()

    for _ in range(Q):

        l,r = LI()

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



            





if __name__ == "__main__":

    main()

prime = [True] * ((10**5) + 1)
prime[0] = False
prime[1] = False
for i in range(2, 10**3):
    if i * i > 10**5:
        break
    if prime[i]:
        for j in range(i, 10**5):
            if i * j > 10**5:
                break
            prime[i * j] = False
prime2017 = [x for x in prime]
prime2017[2] = False
for i in range(3, (10**5) + 1):
    if prime[i]:
        prime2017[i] = prime[(i + 1) // 2]
count = 0
csum = [0] * ((10**5) + 1)
for i in range((10**5) + 1):
    if prime2017[i]:
        count += 1
    csum[i] = count
N = int(eval(input()))
for _ in range(N):
    l, r = list(map(int, input().split()))
    print((csum[r] - csum[l - 1]))

import sys
import heapq
import bisect

mod = 10**9 + 7
dd = ((-1, 0), (1, 0), (0, -1), (0, 1))


def I():
    return int(sys.stdin.readline())


def LI():
    return [int(x) for x in sys.stdin.readline().split()]


def S():
    return sys.stdin.readline()[:-1]


def IR(n):
    return [I() for _ in range(n)]


def GCD(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def LCM(a, b):
    return a * b // GCD(a, b)


def Eratosthenes(N):
    r = [True] * (N + 1)
    r[0] = False
    r[1] = False
    i = 2
    while i * i <= N:
        if r[i]:
            j = i
            while i * j <= N:
                r[i * j] = False
                j += 1
        i += 1
    return r


def main():
    prime = Eratosthenes(10**5)
    prime_2017 = [False] * (10**5 + 1)
    for i in range(3, 10**5 + 1, 2):
        if prime[i]:
            prime_2017[i] = prime[(i + 1) // 2]
    cnt = [0] * (10**5 + 1)
    nxt = 0
    for i in range(1, 10**5 + 1):
        if prime_2017[i]:
            nxt += 1
        cnt[i] = nxt
    Q = I()
    for _ in range(Q):
        l, r = LI()
        print((cnt[r] - cnt[l - 1]))


if __name__ == "__main__":
    main()

-prime = [True] * ((10**5) + 1) -prime[0] = False -prime[1] = False -for i in range(2, 10**3): -    if i * i > 10**5: -        break -    if prime[i]: -        for j in range(i, 10**5): -            if i * j > 10**5: -                break -            prime[i * j] = False -prime2017 = [x for x in prime] -prime2017[2] = False -for i in range(3, (10**5) + 1): -    if prime[i]: -        prime2017[i] = prime[(i + 1) // 2] -count = 0 -csum = [0] * ((10**5) + 1) -for i in range((10**5) + 1): -    if prime2017[i]: -        count += 1 -    csum[i] = count -N = int(eval(input())) -for _ in range(N): -    l, r = list(map(int, input().split())) -    print((csum[r] - csum[l - 1])) +import sys +import heapq +import bisect + +mod = 10**9 + 7 +dd = ((-1, 0), (1, 0), (0, -1), (0, 1)) + + +def I(): +    return int(sys.stdin.readline()) + + +def LI(): +    return [int(x) for x in sys.stdin.readline().split()] + + +def S(): +    return sys.stdin.readline()[:-1] + + +def IR(n): +    return [I() for _ in range(n)] + + +def GCD(a, b): +    while b != 0: +        a, b = b, a % b +    return a + + +def LCM(a, b): +    return a * b // GCD(a, b) + + +def Eratosthenes(N): +    r = [True] * (N + 1) +    r[0] = False +    r[1] = False +    i = 2 +    while i * i <= N: +        if r[i]: +            j = i +            while i * j <= N: +                r[i * j] = False +                j += 1 +        i += 1 +    return r + + +def main(): +    prime = Eratosthenes(10**5) +    prime_2017 = [False] * (10**5 + 1) +    for i in range(3, 10**5 + 1, 2): +        if prime[i]: +            prime_2017[i] = prime[(i + 1) // 2] +    cnt = [0] * (10**5 + 1) +    nxt = 0 +    for i in range(1, 10**5 + 1): +        if prime_2017[i]: +            nxt += 1 +        cnt[i] = nxt +    Q = I() +    for _ in range(Q): +        l, r = LI() +        print((cnt[r] - cnt[l - 1])) + + +if __name__ == "__main__": +    main()