CERI2018D - Largest prime factor


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


Added by:Francky
Date:2018-05-03
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All