# Original solution
import sys
sys.setrecursionlimit(100000)

def isPrime(i):
    if i == 2 or i == 3:
        return True
    elif i % 2 == 0:
        return False
    p = 3
    tmp = i ** 0.5
    while i != 1:
        if i % p == 0:
            return False
        elif p > tmp:
            return True
        else:
            p += 2
    return True


class RSQ_segment_tree:
    """Range Sum Query
    0 indexed
    """

    def __init__(self, init_num, n):
        # represent tree as array
        # parent of k : (k - 1) // 2
        # children of k : 2 * k + 1 and 2 * k + 2
        self.ex = 0
        while(2 ** self.ex < n):
            self.ex += 1
        self.bottom = 2 ** self.ex - 1
        self.tree = [init_num for _ in range(2 ** (self.ex + 1) - 1)]

    def __str__(self):
        tmp = "tree structure\n"
        tree = str(self.tree)
        return tmp + tree + "\n"

    def min_update(self, position, new):
        # chi : child
        # par : parent
        chi = self.bottom + position
        self.tree[chi] = new
        for _ in range(self.ex):
            par = (chi - 1) // 2
            ano_chi = [chi + 1, chi - 1][chi % 2 == 0]
            self.tree[par] = min(self.tree[chi], self.tree[ano_chi])
            chi = par
        return True
    
    def sum_find(self, left, right, first=False):
        """[left, right]"""
        if first is True:    
            left = self.bottom + left
            right = self.bottom + right
        if left == right:
            return self.tree[left]

        ret = 0
        while left < right:
            if left % 2 == 1:
                pass
            else:
                ret -= self.tree[left-1]
                left -= 1

            if right % 2 == 1:
                ret += self.tree[right]
                right -= 1
            # print(left, right)
            left = (left-1)//2
            right = (right-1)//2
        return ret + self.tree[left]
    
    def make_sum(self):
        for i in reversed(list(range(self.bottom))):
            self.tree[i] = self.tree[(i+1)*2] + self.tree[(i+1)*2-1]


def inpl(): return list(map(int, input().split()))

Q = int(eval(input()))
# query = [inpl() for i in range(Q)]
N = 10 ** 5

rsq = RSQ_segment_tree(0, N)
prime = [False] * (N+1)
for i in range(2, N+1):
    prime[i] = isPrime(i)
    rsq.tree[i+rsq.bottom] = int(prime[i] and prime[(i+1)//2])

rsq.make_sum()
# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for _ in range(Q):
    l, r = inpl()
    print((rsq.sum_find(l, r, first=True)))

# Optimized solution
import sys
sys.setrecursionlimit(100000)

def isPrime(i):
    if i < 2:
        return False
    elif i == 2:
        return True
    elif i % 2 == 0:
        return False
    for j in range(3, int(i**0.5)+1, 2):
        if i % j == 0:
            return False
    return True


class RSQ_segment_tree:
    """Range Sum Query
    0 indexed
    """

    def __init__(self, init_num, n):
        # represent tree as array
        # parent of k : (k - 1) // 2
        # children of k : 2 * k + 1 and 2 * k + 2
        self.ex = 0
        while(2 ** self.ex < n):
            self.ex += 1
        self.bottom = 2 ** self.ex - 1
        self.tree = [init_num for _ in range(2 ** (self.ex + 1) - 1)]

    def __str__(self):
        tmp = "tree structure\n"
        tree = str(self.tree)
        return tmp + tree + "\n"

    def min_update(self, position, new):
        # chi : child
        # par : parent
        chi = self.bottom + position
        self.tree[chi] = new
        for _ in range(self.ex):
            par = (chi - 1) // 2
            ano_chi = [chi + 1, chi - 1][chi % 2 == 0]
            self.tree[par] = min(self.tree[chi], self.tree[ano_chi])
            chi = par
        return True
    
    def sum_find(self, left, right, first=False):
        """[left, right]"""
        if first is True:    
            left = self.bottom + left
            right = self.bottom + right
        if left == right:
            return self.tree[left]

        ret = 0
        while left < right:
            if left % 2 == 1:
                pass
            else:
                ret -= self.tree[left-1]
                left -= 1

            if right % 2 == 1:
                ret += self.tree[right]
                right -= 1
            # print(left, right)
            left = (left-1)//2
            right = (right-1)//2
        return ret + self.tree[left]
    
    def make_sum(self):
        for i in reversed(list(range(self.bottom))):
            self.tree[i] = self.tree[(i+1)*2] + self.tree[(i+1)*2-1]


def inpl(): return list(map(int, input().split()))

Q = int(eval(input()))
# query = [inpl() for i in range(Q)]
N = 10 ** 5

rsq = RSQ_segment_tree(0, N)
prime = [False] * (N+1)
for i in range(2, N+1):
    prime[i] = isPrime(i)
    rsq.tree[i+rsq.bottom] = int(prime[i] and prime[(i+1)//2])

rsq.make_sum()
# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for _ in range(Q):
    l, r = inpl()
    print((rsq.sum_find(l, r, first=True)))