### BUGGY CODE ###

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]

        if left % 2 == 1:
            tmpl = 0
        else:
            tmpl = -1 * self.tree[left-1]
            left -= 1

        if right % 2 == 1:
            tmpr = self.tree[right]
            right -= 1
        else:
            tmpr = 0
        # print(left, right)
        return tmpl + tmpr + self.sum_find((left-1)//2, (right-1)//2)
    
    def make_sum(self):
        for i in reversed(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(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))

### FIXED CODE ###

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

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

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


prime = [True] * (N+1)
prime[0] = False
prime[1] = False
for i in range(2, N+1):
    if prime[i] is False:
        continue
    
    tmp = i * 2
    while tmp <= N:
        prime[tmp] = False
        tmp += i

dst = [0] * (N+1)
for i in range(1, N+1):
    dst[i] = dst[i-1] + int(prime[i] and prime[(i+1)//2])

# print(rsq.tree[rsq.bottom:rsq.bottom+10])
for _ in range(Q):
    l, r = inpl()
    print(dst[r]-dst[l-1])