Largest Prime Factor Decoder

You are given an encoded message which consists of several test cases. In each test case, you are given a sequence of positive integers. Your task is to decode the message by finding the largest prime factor of each integer.

More formally, consider an integer \( n \). The largest prime factor \( p \) is the greatest prime number that divides \( n \) exactly. For example, for \( n = 10 \), the prime factors are \( 2 \) and \( 5 \), and the largest is \( 5 \).

The input is provided via stdin and the output must be printed to stdout. Each test case starts with an integer \( N \) which indicates how many numbers follow. For each test case, output a single line containing the decoded message, which is the sequence of largest prime factors for the given numbers in the test case separated by spaces.

Example:

Input:
2
3
10 15 21
4
14 35 49 77
Output:
5 5 7
7 7 7 11

</p>

inputFormat

The first line of the input contains a single integer \( T \) which represents the number of test cases. The following lines describe each test case.

For each test case:

• The first line contains a single integer \( N \), the number of integers in that test case.
• The second line contains \( N \) space-separated positive integers.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing \( N \) integers. Each integer is the largest prime factor of the corresponding input number, in the same order as given in the input. Each output line is printed to standard output (stdout).

## sample

3
3
10 15 21
4
14 35 49 77
2
2 3

5 5 7
7 7 7 11
2 3

</p>