1. #!/usr/bin/env python
2.  
3.  
4. class primaryNumbers:
5.     def nSet(self):
6.         self.numSet = int(input())
7.  
8.     def numIn(self, nSet):
9.         self.dataA = []
10.         self.dataB = []
11.         for i in range(1, (nSet+1)):
12.             lineInput = input()
13.             temp = lineInput.split(' ')
14.             self.dataA.append(int(temp[0]))
15.             self.dataB.append(int(temp[1]))
16.  
17.     def primaryCheck(self, aNum, bNum):
18.         i = 0
19.         self.table = []
20.         self.count = 0
21.  
22.         for testNum in range(aNum, (bNum+1)):
23.             self.table.append(True)
24.  
25.         for testNum in range(aNum, (bNum+1)):
26.             if self.table[i]:
27.                 for x in range(2, (testNum)):
28.                     if testNum % x is 0:
29.                         multiple = int(bNum/testNum) - int(aNum/testNum)
30.                         if multiple is not 0:
31.                             for j in range(0, multiple):
32.                                 self.table[i+(testNum*j)] = False
33.                         break
34.             i += 1
35.  
36.         for d in range(0, len(self.table)):
37.             if self.table[d]:
38.                 self.count += 1
39.  
40. x = primaryNumbers()
41. x.nSet()
42. x.numIn(x.numSet)
43.  
44. for i in range(0, x.numSet):
45.     x.primaryCheck(x.dataA[i], x.dataB[i])
46.     print(x.count)