Prime Replacement

You are given a list of integers. Your task is to replace each prime number in the list with the next prime number. A prime number is defined as a natural number \(p > 1\) that has no positive divisors other than 1 and \(p\) itself. For any prime number \(p\) in the list, find the smallest prime number greater than \(p\) and substitute it in the list.

Example: For the list [2, 3, 4, 5, 6], the prime numbers are 2, 3, and 5. Their respective next primes are 3, 5, and 7. So the final list becomes [3, 5, 4, 7, 6].

inputFormat

The input is read from stdin and consists of two lines:

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

outputFormat

Print to stdout the updated list of integers after replacing each prime with its next prime. The output should be a single line of \(n\) space-separated integers.

5
2 3 4 5 6

3 5 4 7 6