eolymp
bolt
Try our new interface for solving problems
Problems

Almost Prime Numbers

Almost Prime Numbers

Time limit 1 second
Memory limit 128 MiB

Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.

Input data

First line contains an integer n~(n \le 600) which indicates how many sets of inputs are there. Each of the next n lines is a separate test case that contains two integer numbers low and high~(0 < low \le high \le 10^{12}).

Output data

For each test case print in a separate line the number of almost prime integers on a segment [low ... high] inclusive.

Examples

Input example #1
3
1 10
1 20
1 5
Output example #1
3
4
1