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 
# https://codeforces.com/contest/959

import sys

input = lambda: sys.stdin.readline().rstrip()  # faster!


class PrimesUtil:
    def __init__(self, mx):
        assert 1 <= mx
        self.mx = mx
        self.prime_numbers = []
        self.prime = [False] * 2 + [True] * (mx - 1)
        self.factor = [0] * (mx + 1)
        self._run_sieve()

    def _run_sieve(self):
        """Runs the sieve of Eratosthenes (fast version from stackoverflow)."""
        if self.mx >= 2:  # 2
            self.prime_numbers += [2]
            self.prime[4::2] = [False] * ((self.mx - 4) // 2 + 1)
            self.factor[2] = 2
            self.factor[4::2] = [2] * ((self.mx - 4) // 2 + 1)
        for i in range(3, self.mx + 1, 2):  # 3 onwards
            if self.prime[i]:
                self.prime_numbers += [i]
                self.prime[i * i::2 * i] = [False] * (((self.mx + 1) - i * i - 1) // (2 * i) + 1)
                self.factor[i] = i
                self.factor[i * i::2 * i] = [i] * (((self.mx + 1) - i * i - 1) // (2 * i) + 1)

    def is_prime(self, n):
        """Checks whether a number is prime. For numbers larger than self.mx, the Miller-Rabin test is used."""
        assert 1 <= n < 3_317_044_064_679_887_385_961_981
        return self.prime[n] if n <= self.mx else PrimesUtil.is_prime_miller_rabin(n)

    @classmethod
    def is_prime_miller_rabin(cls, n):
        """Checks whether a number is prime according to the Miller–Rabin primality test."""
        assert 1 <= n < 3_317_044_064_679_887_385_961_981
        if n <= 4:
            return n == 2 or n == 3

        d, pow2 = n - 1, 0
        while d % 2 == 0:
            d //= 2
            pow2 += 1

        if n < 2_152_302_898_747:
            bases = [2, 3, 5, 7, 11]
        elif n < 341_550_071_728_321:
            bases = [2, 3, 5, 7, 11, 13, 17]
        else:
            bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

        for b in bases:
            x = pow(b, d, n)
            if x == 0 or x == 1 or x == n - 1:
                continue
            for _ in range(1, pow2):
                x = (x * x) % n
                if x == 1:
                    return False
                if x == n - 1:
                    break
            if x != n - 1:
                return False
        return True

    def factorise(self, n):
        """Returns a list of tuples (prime, exponent) representing the prime factorisation of n.
         Performance depends on whether the number is from [1, self.mx] or from [self.mx+1, self.max**2]."""
        assert 1 <= n <= self.mx ** 2
        prime_factorisation = []
        if n <= self.mx:
            while n > 1:
                prime_number, exp = self.factor[n], 0
                while n % prime_number == 0:
                    exp += 1
                    n //= prime_number
                prime_factorisation += [(prime_number, exp)]
        else:
            for prime_number in self.prime_numbers:
                if prime_number ** 2 > n:
                    break
                if n % prime_number == 0:
                    exp = 0
                    while n % prime_number == 0:
                        exp += 1
                        n //= prime_number
                    prime_factorisation += [(prime_number, exp)]
            if n > 1:
                prime_factorisation += [(n, 1)]
        return prime_factorisation

    def divisors(self, n):
        """Returns all divisors of a number as an unsorted list.
        Performance depends on whether number is from [1, self.mx] or from [self.mx+1, self.max**2]."""
        assert 1 <= n <= self.mx ** 2
        from itertools import product
        from math import prod
        div = []
        prime_factorisation = self.factorise(n)
        exp_ranges = [list(range(exp + 1)) for (_, exp) in prime_factorisation]
        for exponents in product(*exp_ranges):
            div += [prod(prime_factorisation[i][0] ** exponents[i] for i in range(len(prime_factorisation)))]
        return div


n = int(input())  # 1 <= n <= 10**5
a = list(map(int, input().split()))  # 2 <= n <= 10**5

b = [0] * n
PU = PrimesUtil(10 ** 6)
primes_used = set()
larger = False
next_number = 1
for i, v in enumerate(a):
    if not larger:
        pf = PU.factorise(v)
        ok = all(p not in primes_used for p, _ in pf)
        if ok:
            b[i] = v
            primes_used |= {p for p, _ in pf}
        else:
            x = v
            while True:
                x += 1
                pf = PU.factorise(x)
                ok = all(p not in primes_used for p, _ in pf)
                if ok:
                    b[i] = x
                    larger = True
                    primes_used |= {p for p, _ in pf}
                    break

    else:
        while True:
            next_number += 1
            pf = PU.factorise(next_number)
            ok = all(p not in primes_used for p, _ in pf)
            if ok:
                b[i] = next_number
                primes_used |= {p for p, _ in pf}
                break

print(*b)
