#1126. zxh的温故知新

This problem is similar to ICPC 2019 Xuzhou Regional C, but they are actually not the same.

Sheauhaw likes to play with positive integers, especially the less-3 numbers in positive integers.

Less-3 number is a special group of positive integers, all of which can be divided by less than three positive integers.

For example, $7$ is a less-3 number. There are two positive integers that divide $7$ by $1$ and $7$. $25$ is not a less-3 number. There are $1$, $5$ and $25$ that can divide $25$.

Now, Sheauhaw is curious about how many less-3 numbers are included between positive integers $L$ and $R$. Please help the curious Sheauhaw to answer his questions.

The first line has a positive integer of $T$, which represents the total number of test data.

Each test data is a line of two integers $L,R$.

Please output one line for each test data.

For each test data, please output the proportion of less-3 numbers between $L$ and $R$ (including $L$ and $R$).

Standard Input

3
7 7
25 25
5 14

Standard Output

1
0
4

$1≤T≤50$

$1 \le L \le R \le 10^7$