It's really a nice Number Theory problem.

In the problem statement you can note that r, p -both greater than 1 from it you can conclude the following:

• When we factor the number of prime factors, you can note that the lowest exponent of these factors is 2.
• Above the cube root of the number, there is one prime factor and the exponent of this factor is 2 or that there are no factors above the cube root.

From the previous observations, you can find the factors which are less than or equal the cube root in for-loop then you can check if there is a prime factor above the cube root or not.

In this way you can calculate prime factors for K with time complexity O($$$\sqrt[3]{K}$$$) then from the prime factors, you can find the divisors, and then the answer will be the frequency of the divisors in Array C.

AC solution

The Time Complexity O($$$Q\times\sqrt[3]{K}$$$)