Mahmoud has an array *a* consisting of *n* integers. He asked Ehab to find another array *b* of the same length such that:
 -  *b* is lexicographically greater than or equal to *a*. -  *b*<sub class="lower-index">*i*</sub> ≥ 2. -  *b* is pairwise coprime: for every 1 ≤ *i* &lt; *j* ≤ *n*, *b*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*j*</sub> are coprime, i. e. *GCD*(*b*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*j*</sub>) = 1, where *GCD*(*w*, *z*) is the greatest common divisor of *w* and *z*. 
Ehab wants to choose a special array so he wants the lexicographically minimal array between all the variants. Can you find it?

An array *x* is lexicographically greater than an array *y* if there exists an index *i* such than *x*<sub class="lower-index">*i*</sub> &gt; *y*<sub class="lower-index">*i*</sub> and *x*<sub class="lower-index">*j*</sub> = *y*<sub class="lower-index">*j*</sub> for all 1 ≤ *j* &lt; *i*. An array *x* is equal to an array *y* if *x*<sub class="lower-index">*i*</sub> = *y*<sub class="lower-index">*i*</sub> for all 1 ≤ *i* ≤ *n*.
The first line contains an integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>), the number of elements in *a* and *b*.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (2 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>), the elements of *a*.
Note that in the second sample, the array is already pairwise coprime so we printed it.
5
2 3 5 4 13
2 3 5 7 11 
3
10 3 7
10 3 7 
5
7 10 2 5 5
7 10 3 11 13 
7
20 9 7 6 7 9 15
20 9 7 11 13 17 19 
10
5 3 2 2 3 3 3 4 2 5
5 3 2 7 11 13 17 19 23 29 
3
3 18 2
3 19 2 
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fast_prime_factorization(n):
    d = [(i + 1) % 2 * 2 for i in range(n + 1)]
    d[0], d[1] = 0, 1
    for i in range(3, n + 1):
        if d[i]:
            continue
        for j in range(i, n + 1, 2 * i):
            if not d[j]:
                d[j] = i
    return d

n = int(input())
a = list(map(int, input().split()))
l = 3 * pow(10, 6)
d = fast_prime_factorization(l)
visit = [0] * l
ans = []
for i in a:
    u = i
    s = set()
    while d[u] ^ u:
        s.add(u // d[u])
        u //= d[u]
    if u ^ 1:
        s.add(u)
    ok = 1
    for j in s:
        if visit[j]:
            ok = 0
    if ok:
        ans.append(i)
        for j in s:
            visit[j] = 1
    else:
        j = i + 1
        while d[j] ^ j or visit[j]:
            j += 1
        ans.append(j)
        visit[j] = 1
        break
i = 2
while len(ans) ^ n:
    if d[i] == i and not visit[i]:
        ans.append(i)
    i += 1
sys.stdout.write(" ".join(map(str, ans)))