#!/usr/bin/env python
 
 
class primaryNumbers:
    def nSet(self):
        self.numSet = int(input())
 
    def numIn(self, nSet):
        self.dataA = []
        self.dataB = []
        for i in range(1, (nSet+1)):
            lineInput = input()
            temp = lineInput.split(' ')
            self.dataA.append(int(temp[0]))
            self.dataB.append(int(temp[1]))
 
    def primaryCheck(self, aNum, bNum):
        i = 0
        self.table = []
        self.count = 0
 
        for testNum in range(aNum, (bNum+1)):
            self.table.append(True)
 
        for testNum in range(aNum, (bNum+1)):
            if self.table[i]:
                for x in range(2, (testNum)):
                    if testNum % x is 0:
                        multiple = int(bNum/testNum) - int(aNum/testNum)
                        if multiple is not 0:
                            for j in range(0, multiple):
                                self.table[i+(testNum*j)] = False
                        break
            i += 1
 
        for d in range(0, len(self.table)):
            if self.table[d]:
                self.count += 1
 
x = primaryNumbers()
x.nSet()
x.numIn(x.numSet)
 
for i in range(0, x.numSet):
    x.primaryCheck(x.dataA[i], x.dataB[i])
    print(x.count)