#!usr/bin/env python3

from collections import defaultdict

from collections import deque

from heapq import heappush, heappop

import sys

import math

import bisect

import random

def LI(): return list(map(int, sys.stdin.readline().split()))

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

def LS():return list(map(list, sys.stdin.readline().split()))

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

def IR(n):

    l = [None for i in range(n)]

    for i in range(n):l[i] = I()

    return l

def LIR(n):

    l = [None for i in range(n)]

    for i in range(n):l[i] = LI()

    return l

def SR(n):

    l = [None for i in range(n)]

    for i in range(n):l[i] = S()

    return l

def LSR(n):

    l = [None for i in range(n)]

    for i in range(n):l[i] = SR()

    return l

mod = 1000000007



#A

def A():

    return



#B

def B():

    return



#C

def C():

    return



#D

if __name__ == "__main__":

    def check(n):

        if n == 1:

            return False

        i = 2

        while i*i <= n:

            if n%i == 0:

                return False

            i += 1

        return True

    f = [0 for i in range(100001)]

    for i in range(1,100001):

        f[i] += f[i-1]

        if check(i):

            if check((i+1)//2):

                f[i] += 1

    q = I()

    for i in range(q):

        l,r = LI()

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



#E

def E():

    return



#F

def F():

    return



#G

def G():

    return



#H

def H():

    return



#Solve

#!usr/bin/env python3

from collections import defaultdict,deque

from heapq import heappush, heappop

from itertools import permutations

import sys

import math

import bisect

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

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

def LS():return [list(x) for x in sys.stdin.readline().split()]

def S():

    res = list(sys.stdin.readline())

    if res[-1] == "\n":

        return res[:-1]

    return res

def IR(n):

    return [I() for i in range(n)]

def LIR(n):

    return [LI() for i in range(n)]

def SR(n):

    return [S() for i in range(n)]

def LSR(n):

    return [LS() for i in range(n)]



sys.setrecursionlimit(1000000)

mod = 1000000007



def solve():

    n = 10**5+1

    p = 2

    f = [1]*(n+1)

    f[0] = 0

    f[1] = 0

    while p <= n:

        while p <= n and not f[p]:

            p += 1

        j = 2*p

        while j <= n:

            f[j] = 0

            j += p

        p += 1

    s = [1 if f[i] and f[(i+1)>>1] and i&1 else 0 for i in range(n+1)]

    for i in range(n):

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

    q = I()

    for _ in range(q):

        l,r = LI()

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

    return



#Solve

if __name__ == "__main__":

    solve()

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random


def LI():
    return list(map(int, sys.stdin.readline().split()))


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


def LS():
    return list(map(list, sys.stdin.readline().split()))


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


def IR(n):
    l = [None for i in range(n)]
    for i in range(n):
        l[i] = I()
    return l


def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):
        l[i] = LI()
    return l


def SR(n):
    l = [None for i in range(n)]
    for i in range(n):
        l[i] = S()
    return l


def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):
        l[i] = SR()
    return l


mod = 1000000007
# A
def A():
    return


# B
def B():
    return


# C
def C():
    return


# D
if __name__ == "__main__":

    def check(n):
        if n == 1:
            return False
        i = 2
        while i * i <= n:
            if n % i == 0:
                return False
            i += 1
        return True

    f = [0 for i in range(100001)]
    for i in range(1, 100001):
        f[i] += f[i - 1]
        if check(i):
            if check((i + 1) // 2):
                f[i] += 1
    q = I()
    for i in range(q):
        l, r = LI()
        print((f[r] - f[l - 1]))
# E
def E():
    return


# F
def F():
    return


# G
def G():
    return


# H
def H():
    return


# Solve

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect


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


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


def LS():
    return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


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


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n = 10**5 + 1
    p = 2
    f = [1] * (n + 1)
    f[0] = 0
    f[1] = 0
    while p <= n:
        while p <= n and not f[p]:
            p += 1
        j = 2 * p
        while j <= n:
            f[j] = 0
            j += p
        p += 1
    s = [1 if f[i] and f[(i + 1) >> 1] and i & 1 else 0 for i in range(n + 1)]
    for i in range(n):
        s[i + 1] += s[i]
    q = I()
    for _ in range(q):
        l, r = LI()
        print((s[r] - s[l - 1]))
    return


# Solve
if __name__ == "__main__":
    solve()

-from collections import defaultdict -from collections import deque +from collections import defaultdict, deque +from itertools import permutations -import random -    return list(map(int, sys.stdin.readline().split())) +    return [int(x) for x in sys.stdin.readline().split()] -    return list(map(list, sys.stdin.readline().split())) +    return [list(x) for x in sys.stdin.readline().split()] -    return list(sys.stdin.readline())[:-1] +    res = list(sys.stdin.readline()) +    if res[-1] == "\n": +        return res[:-1] +    return res -    l = [None for i in range(n)] -    for i in range(n): -        l[i] = I() -    return l +    return [I() for i in range(n)] -    l = [None for i in range(n)] -    for i in range(n): -        l[i] = LI() -    return l +    return [LI() for i in range(n)] -    l = [None for i in range(n)] -    for i in range(n): -        l[i] = S() -    return l +    return [S() for i in range(n)] -    l = [None for i in range(n)] -    for i in range(n): -        l[i] = SR() -    return l +    return [LS() for i in range(n)] +sys.setrecursionlimit(1000000) -# A -def A(): -    return -# B -def B(): -    return - - -# C -def C(): -    return - - -# D -if __name__ == "__main__": - -    def check(n): -        if n == 1: -            return False -        i = 2 -        while i * i <= n: -            if n % i == 0: -                return False -            i += 1 -        return True - -    f = [0 for i in range(100001)] -    for i in range(1, 100001): -        f[i] += f[i - 1] -        if check(i): -            if check((i + 1) // 2): -                f[i] += 1 +def solve(): +    n = 10**5 + 1 +    p = 2 +    f = [1] * (n + 1) +    f[0] = 0 +    f[1] = 0 +    while p <= n: +        while p <= n and not f[p]: +            p += 1 +        j = 2 * p +        while j <= n: +            f[j] = 0 +            j += p +        p += 1 +    s = [1 if f[i] and f[(i + 1) >> 1] and i & 1 else 0 for i in range(n + 1)] +    for i in range(n): +        s[i + 1] += s[i] -    for i in range(q): +    for _ in range(q): -        print((f[r] - f[l - 1])) -# E -def E(): -    return - - -# F -def F(): -    return - - -# G -def G(): -    return - - -# H -def H(): +        print((s[r] - s[l - 1])) +if __name__ == "__main__": +    solve()