Description:


著名核物理专家 Picks 提出了核聚变特征值这一重要概念。

核聚变特征值分别为 \(x\)\(y\) 的两个原子进行核聚变,能产生数值为 \(sgcd(x,y)\) 的核聚变反应强度。

其中, \(sgcd(x,y)\) 表示 \(x\)\(y\) 的次大公约数,即能同时整除 \(x,y\) 的正整数中第二大的数。如果次大公约数不存在则说明无法核聚变, 此时 \(sgcd(x,y)=-1\)

现在有 \(n\) 个原子,核聚变特征值分别为 \(a_1,a_2,\ldots ,a_n\) 。然后 Picks 又从兜里掏出一个核聚变特征值为 \(a_1\) 的原子,你需要计算出这个原子与其它 \(n\) 个原子分别进行核聚变反应时的核聚变反应强度,即 \(sgcd(a_1,a_1),sgcd(a_1,a_2),\ldots ,sgcd(a1,a_n)\)

Input:


第一行一个正整数 \(n\)

第二行 \(n\) 个用空格隔开的正整数,第 \(i\) 个为 \(a_i\)

Output:


一行 \(n\) 个用空格隔开的整数,第 \(i\) 个表示 \(sgcd(a_1,a_i)\)

C/C++ 输入输出 long long 时请用 %lld。由于本题数据量较大,建议不要使用 cin/cout 进行输入输出。

Sample Input:


Sample Output:


题解:


UR的题目貌似没有那么难(=_=这是第一题)

根据公约数的性质,次大公约数即为最大公约数的次大约数。

因为每一次都是对 \(a_1\) 最大公约数,所以最大公约数一定为 \(a_1\) 的约数。

我们把 \(a_1\) 的质因数弄出来,然后每一次找到能够整除最大公约数的第一个质数,就可以了。

注意判断一下特殊情况。