M. Степень: много запросов

Для каждого числа $A$ найдите наименьшее натуральное $N$ такое, что $N^N$ делится на $A$.

Первая строка содержит число запросов $q$ ($1 \le q \le 100$).

Каждая из следующих $q$ строк содержит одно число $A$ ($1 \le A \le 10^9$).

Для каждого запроса выведите одно число.