eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 4 seconds
Memory limit 64 MiB

Вам дано натуральное число n > 1. Рассмотрим все различные простые делители n. Каждый из них входит в разложение n на простые множители в какой-то степени. Требуется найти среди показателей этих степеней максимальный.

Input data

В первой строке входного файла задано натуральное число T500, количество натуральных чисел n в файле. В последующих T строках заданы сами эти числа. Гарантируется, что каждое из них не превосходит 10^18.

Output data

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

Examples

Input example #1
5
2
12
108
36
65536
Output example #1
1
2
3
2
16
Author Anton Lunev
Source Winter School, Kharkov, 2011, Day 6