Максимальна степінь простого

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

Вхідні дані

У першому рядку вхідного файлу задано натуральне число T ≤ 500, кількість натуральних чисел n у файлі. У наступних T рядках задано самі ці числа. Гарантиується, що кожне з них не перевищує 10^18.

Вихідні дані

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

Приклади