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
from array import array

input = lambda: sys.stdin.buffer.readline().decode().rstrip()
inp = lambda dtype: [dtype(x) for x in input().split()]
debug = lambda *x: print(*x, file=sys.stderr)
ceil_ = lambda a, b: (a + b - 1) // b
sum_n = lambda n: (n * (n + 1)) // 2
get_bit = lambda x, i: (x >> i) & 1
Mint, Mlong, out = 2 ** 30 - 1, 2 ** 62 - 1, []


def count_prime(n):
    prim = array('i', [0] * (n + 1))

    for i in range(2, n + 1):
        if not prim[i]:
            for j in range(i, n + 1, i):
                prim[j] = i
    return prim


def prime_factor(x):
    fac = set()
    while x > 1:
        div = prim[x]
        fac.add(div)

        while x % div == 0:
            x //= div
    return fac


def solve(i):
    global primes
    while True:
        cfacs = prime_factor(ans[i])
        for j in cfacs:
            if j in primes: break
        else:
            primes |= cfacs
            break
        ans[i] += 1


def finish(ix):
    cur = 2
    for i in range(ix, n):
        ans.append(cur)
        solve(i)
        cur = ans[-1] + 1


prim = count_prime(10 ** 7)
for _ in range(1):
    n, a = int(input()), array('i', inp(int))
    primes, ans = set(), array('i')

    for i in range(n):
        ans.append(a[i])
        solve(i)

        if a[i] < ans[i]:
            finish(i + 1)
            break

    out.append(' '.join(map(str, ans)))
print('\n'.join(map(str, out)))
