Problem G: JYL学长的数列

Problem G: JYL学长的数列

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 43  Solved: 7
[Submit] [Status] [Web Board] [Creator:]

Description

现在JYL学长有一个序列a,zser想让他找到一个序列b,当然因为zser和JYL学长一样胖,所以
b序列应该也和a序列一样长。
但是我们要求b序列要有以下的规则:
1.b序列的字典序要大于等于a
2.b[i] >= 2
3.并且对于每一对i , j(i < j)都有gcd(b[i],b[j]) = 1
但是JYL学长非常挑剔,他还要求zser找到的序列b的字典序最小。



输出该序列b

Input

第一行输入一个n,代表序列a的个数(1 <= n <= 1e5) 
第二行输入n个数,代表序列a[i](2 <= a[i] <= 1e5)

Output

输入n个数,代表b序列,每个数以空格隔开,行末尾没有空格

Sample Input Copy

5
13 12 4 7 9

Sample Output Copy

13 12 5 7 11