The task is to print the largest prime factor of an integer.

Input

The first line of the input consist of a single integer number t which determines the number of tests.

In each of next t lines there is a single integer number n.

Constraints

• 0 < t ≤ 1000
• 1 < n ≤ 1 000 000 000

Output

Print the largest prime factor of n

Example

Input:
3
10
11
12
Output:
5
11
3