Replace With Next Primes

Given a list of integers, your task is to replace each number with the smallest prime number that is greater than or equal to the original number. A number \(p\) is called prime if it satisfies \(p > 1\) and its only positive divisors are 1 and \(p\) (i.e. \(p\) has no divisors other than 1 and itself).

For example, for the input list [10, 15, 17, 25], the output should be [11, 17, 17, 29] because:

• The next prime \(\geq 10\) is 11.
• The next prime \(\geq 15\) is 17.
• 17 is already a prime, so it stays 17.
• The next prime \(\geq 25\) is 29.

Note: You should use the standard input and output (stdin and stdout) for handling input and output.

inputFormat

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

For example:

4
10 15 17 25

outputFormat

Output a single line containing \(n\) space-separated integers, where each integer is the smallest prime number that is greater than or equal to the corresponding input integer.

For example:

11 17 17 29

## sample

4
10 15 17 25

11 17 17 29