Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito está estudiando matemática y se ha encontrado un ejercicio muy peculiar, nuestra tarea es ayudar a solucionar el ejercicio.

Se tiene una secuencia de números enteros $S$, donde $S_0 = 1$, $S_1 = 2$, …, $S_i = S_{i-1} + DIV(S_{i-1})$ donde $DIV(x)$ es la cantidad de divisores de $X$. Por lo que $S = \{1, 2, 4, 7, 9, 12,18, ...\}$. Dados dos números naturales $M$ y $N$, se debe de encontrar la cantidad de números que pertenecen a $S$ que están en el intervalo $[M, N]$.

Input

La primera línea de la entrada es un entero $C$ ($1 \lt C \lt 100000$) que representa la cantidad de casos de prueba, por cada caso de prueba en una línea hay dos enteros $M$ y $N$ ($1 \leq M \leq N \leq 1000000$) separados por un espacio.

Output

Por cada caso de prueba se imprime la respuesta del ejercicio.

Sample test(s)