Problem 003

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Input Format

First line contains T, the number of test cases. This is followed by T lines each containing an integer N.

Output Format

For each test case, display the largest prime factor of N.

Sample Input

2
10
17

Sample Output

5
17

Explanation

• Prime factors of 10 are {2, 5}, largest is 5.
• Prime factors of 17 is 17 itself, hence largest is 17.