We can easily precalculate the prime divisors of each number using .
For each test case, We will connect each numbers node, with its prime divisors node.
We can simply use to find the number of connected components and their size. While counting, we have to exclude the nodes that are not in range from to .
Time Complexity: for precalculation where N = . And for test cases.