Largest Prime Factor

Given a positive integer \(n\), determine its largest prime factor. Every number \(n\) can be expressed as a product of prime factors, i.e., \(n = p_1^{\alpha_1}\times p_2^{\alpha_2}\times \cdots \times p_k^{\alpha_k}\). Your task is to find the largest among these primes, i.e., \(\max\{p_1, p_2, \dots, p_k\}\).

If \(n\) is prime itself, then the largest prime factor is \(n\) itself.

inputFormat

The first line contains a single integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains one integer \(n\).

outputFormat

For each test case, output the largest prime factor of \(n\) on a new line.

3
10
15
21

5
5
7