Largest Prime Factor Problem Statement

You are given a positive integer n. Your task is to identify the largest prime factor of this given positive integer.

If there is no prime factor for a given integer, output -1.

Input:

The first line of input contains an integer T representing the number of test cases. The subsequent T lines each contain a positive integer n.

Output:

For each test case, output the largest prime factor of the given positive integer, on a separate line.

Example:

Input:

2
10
17

Output:

5
17

Explanation:

• For n = 10, the prime factors are 2 and 5, thus largest is 5.
• For n = 17, since 17 is a prime number itself, 17 is the largest prime factor.

Constraints:

• 1 ≤ T ≤ 50
• 1 ≤ n ≤ 10^9