Вам задано натуральне число \textbf{n} > \textbf{1}. Розглянемо всі різні прості дільники \textbf{n}. Кожен з них входить у розклад \textbf{n} на прості множники у якійсь степені. Потрібно знайти серед показників цих степенів максимальний. \InputFile У першому рядку вхідного файлу задано натуральне число \textbf{T} ≤ \textbf{500}, кількість натуральних чисел \textbf{n} у файлі. У наступних \textbf{T} рядках задано самі ці числа. Гарантиується, що кожне з них не перевищує \textbf{10^18}. \OutputFile Для кожного натурального числа \textbf{n} з вхідного файлу виведіть у окремому рядку максимальну степінь входження простого числа у розклад \textbf{n} на прості множники.