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 
class SegTree():

    def __init__(self, N, function=max, basement=0):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(1 << (self.K+1)+1)

    def all_update(self, LIST):
        # a[i] -> LIST[i] for all i
        assert len(LIST) < self.n
        X = 1 << (self.K)
        for i, v in enumerate(LIST):
            self.seg[i + X] = v
        for i in range(X - 1, 0, - 1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        # a[i] -> value
        X = 1 << (self.K)
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def get_value(self, I):
        # a[i]
        return self.seg[I + (1 << (self.K))]

    def query(self, L, R):
        # f [L,R)
        num = 1 << (self.K)
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_min_index(self, L, R, X):
        return self.fmi(L, R, X, 1, 0, 1 << (self.K))

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] < x or r <= a or b <= l:
            return -1
        else:
            if k >= (1 << self.K):
                return k-(1 << self.K)
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


n = int(input())
a = list(map(int, input().split()))
MAX = 1500000
STILL_EQUAL = True
BASE = [1]*(MAX + 1)
Q = SegTree(MAX + 10)
Q.all_update(BASE)
b = []
SEEN = [False]*(MAX + 1)
SUBSTRACTED = [False]*(MAX + 1)

PRIMES = [[] for _ in range(MAX + 1)]
isprime = [True]*(MAX + 1)
isprime[1] = False
for i in range(2, MAX + 1):
    if isprime[i] == False:
        continue
    PRIMES[i].append(i)
    for j in range(2*i, MAX + 1, i):
        isprime[j] = False
        PRIMES[j].append(i)


for i, v in enumerate(a):

    if STILL_EQUAL:
        pos = Q.find_min_index(v, MAX+1, 1)
        Q.update(pos, 0)
        b.append(pos)
        if pos > v:
            STILL_EQUAL = False
    else:
        pos = Q.find_min_index(2, MAX+1, 1)
        Q.update(pos, 0)
        b.append(pos)

    if pos > 1 and SEEN[pos] == False:
        SEEN[pos] = True
        for p in PRIMES[pos]:
            if SUBSTRACTED[p] == False:
                for num in range(p, MAX + 1, p):
                    if SUBSTRACTED[num] == False:
                        SUBSTRACTED[num] = True
                        Q.update(num, 0)

print(*b)

