Вам задано натуральне число n (n > 1). Розглянемо всі різні прості дільники n. Кожен з них входить у розклад n на прості множники у якійсь степені. Потрібно знайти серед показників цих степенів мінімальний.
У першому рядку задано кількість натуральних чисел t (t ≤ 100000). У наступних t рядках задано самі ці числа. Гарантується, що кожне з них не перевищує 10^18
.
Для кожного вхідного натурального числа n виведіть в окремому рядку мінімальну степінь входження простого числа у розклад n на прості множники.