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 
def find_gcd(a1,a2):
  if a1>a2:
    smaller = a2
  else:
    smaller = a1
  for i in range(smaller,0,-1):
    if a1%i == 0 and a2%i == 0:
      return i

def check_noncoprime_loc(test_list): 
  for i in range(1,len(test_list)):
    for j in range(0,i):
      gcd = find_gcd(test_list[i],test_list[j])
      if gcd != 1:
        return i
  return i+1

def find_coprime_num(test_list):
  num = 1
  loc_p = 0
  while (loc_p != len(test_list)+1):
    num = num + 1
    new_list = []
    new_list.extend(test_list)
    new_list.append(num)
    loc_p = check_noncoprime_loc(new_list)
  return num

n = int(input())
ip_list = list(map(int,input().split()))
loc = check_noncoprime_loc(ip_list)
if loc == n:
  print(*ip_list,sep=' ')
else:
  op_list = ip_list[0:loc]
  for i in range(loc,n):
    op_list.append(find_coprime_num(op_list))
  print(*op_list,sep=' ')