B - Divisores exactos

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, Python, ... (details)

En la galaxia Messier 83 están haciendo estudios sobre criptografía con el objetivo de encontrar una nueva codificación para los mensajes secretos que se envían. Han determinado los grandes sabios que la mejor forma de encriptar es a través de llaves secretas que consisten en un número $K$ y un rango de enteros $[A, B]$, de forma tal que que para desencriptar es necesario encontrar la cantidad de números $X \in [A, B]$ que tengan exactamente $K$ divisores. Han llegado varios mensajes secretos y es tu deber descifrarlos.

Input

Línea 1 : un entero $Q$ $(1 \le Q \le 10^5)$ indicando la cantidad de preguntas a responder.
Línea 2..Q+1 : tres enteros $A$, $B$ $(1 \le A \le B \le 10^7)$ y $K$ $(1 \le K)$, que representan los extremos del intervalo y la cantidad de divisores buscada, respectivamente.

Output

Línea 1 ..Q : por cada pregunta, una línea con un entero indicando la cantidad de números en $[A, B]$ que tienen exactamente $K$ divisores.

Sample test(s)

Input
8 10 20 4 10 20 3 10 20 2 1 100 3 40 67 5 40 67 4 40 100 8 2 100 9
Output
3 0 4 4 0 7 8 2