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

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

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

现在有 nn 个原子，核聚变特征值分别为 a1,a2,…,ana1,a2,…,an。然后 Picks 又从兜里掏出一个核聚变特征值为 a1a1 的原子，你需要计算出这个原子与其它 nn 个原子分别进行核聚变反应时的核聚变反应强度，即 sgcd(a1,a1),sgcd(a1,a2),…,sgcd(a1,an)sgcd(a1,a1),sgcd(a1,a2),…,sgcd(a1,an)。

第一行一个正整数 nn。

第二行 nn 个用空格隔开的正整数，第 ii 个为 aiai。

一行 nn 个用空格隔开的整数，第 ii 个表示 sgcd(a1,ai)sgcd(a1,ai)。

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

测试点编号    n、ai的规模
1、2                 n=1，ai≤10^9
3、4、5、6        n≤10^4，ai≤10^9
7、8、9、10      n≤10^5，ai≤10^12

算法 最大公约数 最小公倍数