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

What is the largest prime factor of a given number N?

Input Format

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

Constraints 1 ≤ T ≤ 100 10 ≤ N ≤ 10^12

Output Format

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