Вам дано натуральное число \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} на простые множители.