Вам задано натуральне число n (n > 1). Розглянемо всі різні прості дільники n. Кожен з них входить у розклад n на прості множники у якійсь степені. Потрібно знайти серед показників цих степенів мінімальний.

Вхідні дані

У першому рядку задано кількість натуральних чисел t (t ≤ 100000). У наступних t рядках задано самі ці числа. Гарантується, що кожне з них не перевищує 1018.

Вихідні дані

Для кожного вхідного натурального числа n виведіть в окремому рядку мінімальну степінь входження простого числа у розклад n на прості множники.