Maximum degree of a prime

You are given a natural number n > 1. For each distinct prime divisor of n, it appears in the prime factorization of n raised to a certain power. Your task is to determine the highest of these exponents.

Input

The first line of the input contains a natural number T ≤ 500, representing the number of natural numbers n provided. The following T lines contain these numbers. It is guaranteed that each number does not exceed 10^18.

Output

For each natural number n from the input, output the maximum power of a prime number in its prime factorization on a separate line.

Examples