SP8238 NFACTOR - N-Factorful

A number is called **n**-factorful if it has exactly **n** distinct prime factors. Given positive integers **a**, **b**, and **n**, your task is to find the number of integers between **a** and **b**, inclusive, that are **n**-factorful. We consider 1 to be 0-factorful.

Your input will consist of a single integer **T** followed by a newline and **T** test cases. Each test cases consists of a single line containing integers **a**, **b**, and **n** as described above. **T** > 10000 1 a b $ ^{6} $ 0 n

Output for each test case one line containing the number of **n**-factorful integers in \[**a**, **b**\].