Highest Frequency Prime Factor

You are given a list of integers. For each integer n in the list:

• If n < 2, output n as is.
• If n ≥ 2, compute its prime factorization. Write \( n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \) where \( p_i \) are prime factors and \( a_i \) are positive integers. Then, among all \( p_i \), find the prime factor whose exponent \( a_i \) is highest. In case of a tie, choose the smallest such prime factor. Output that prime factor.

For example, for 18, we have 18 = 2¹ × 3², so the answer is 3.

inputFormat

The input is given in two lines from STDIN:

• The first line contains an integer N representing the number of elements in the array.
• The second line contains N space-separated integers.

outputFormat

Print a single line to STDOUT containing N space-separated integers. For each integer in the input, if it is less than 2, print it as is; otherwise, print the prime factor with the highest frequency (choosing the smallest in case of a tie).

5
18 28 15 1 97

3 2 3 1 97