Nearest Prime Replacement

You are given a list of integers. For each integer, you need to replace it with its nearest prime number. If the integer is already a prime, it remains unchanged. In case there is a tie between two primes, choose the smaller one.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Mathematically, an integer \( p \) is prime if \( p > 1 \) and for every integer \( d \) such that \( 1 < d < p \), \( d \) does not divide \( p \).

Note: Use the standard definition of prime numbers and handle the input and output through the standard input (stdin) and standard output (stdout) respectively.

inputFormat

The first line of input contains an integer \( n \) representing the number of elements in the list. The following line contains \( n \) space-separated integers.

Example:

5
4 10 27 38 59

outputFormat

Output a single line containing \( n \) space-separated integers where each integer is replaced with its nearest prime number.

Example:

3 11 29 37 59

## sample

5
4 10 27 38 59

3 11 29 37 59