Replace Primes with Next Prime

You are given a list of integers. Your task is to replace each prime number in the list with the next prime number that is greater than it.

Recall that a prime number \(p\) is an integer greater than 1 that has no divisors other than 1 and \(p\) itself.

For example, if the input list is [2, 3, 5, 8, 13, 17], then the output should be [3, 5, 7, 8, 17, 19] since 2, 3, 5, 13, 17 are prime and their corresponding next primes are 3, 5, 7, 17, and 19 respectively.

inputFormat

The first line of input contains an integer \(n\), the number of elements in the list.

The second line contains \(n\) space-separated integers.

outputFormat

Output the modified list in a single line where each element is separated by a space. For each integer, if it is a prime number, output the next prime number; otherwise, output the number unchanged.

6
2 3 5 8 13 17

3 5 7 8 17 19