The number is powerful. Let the prime factorization of be , then the prime factorization of will be . So the power of each prime of is a multiple of .
Let the prime factorization of be and the maximum among be . If , then must be greater than or equal to . As we know, is a powerful number, is a probable value of and we don’t need to care about the values greater than . There may exist some smaller value than which is powerful. To find them, we can iterate from to and for each , we want to find the minimum value required to make in the form . The number is in the form iff the power of each prime divisor of is a multiple of . So, for each , we can multiply each prime the minimum number of times such that the power of that prime is a multiple of . The answer is the minimum among all such .
The only exception is when is . In this case, the answer is . Time complexity is for each test case where is the total number of primes less than .