Hidden Graph

We can easily precalculate the prime divisors of each number using $Sieve of Eratosthenes$.

For each test case, We will connect each numbers node, with its prime divisors node.
We can simply use $BreadthFirst Search$ to find the number of connected components and their size. While counting, we have to exclude the nodes that are not in range from $L$ to $R$.

Time Complexity: $O( N × log(N) )$ for precalculation where N = $10^6$. And $O(T × R × Log(R))$ for test cases.