Largest Prime Factor

You are given a positive integer \(n\). Your task is to determine its largest prime factor. If \(n\) is prime, then \(n\) itself is its largest prime factor. Note that the number can be very large, so an efficient factorization method is needed. Furthermore, you will be given several test cases from the standard input; for each test case, output the largest prime factor in a separate line.

inputFormat

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

outputFormat

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

3
10
15
21

5
5
7