题目描述

定义 $\operatorname{sgcd}(x,y)$ 表示 $x,y$ 的次大公因数，即能同时整除 $x,y$ 的正整数中第二大的数。

特别的，若不存在次大公因数则定义 $\operatorname{sgcd}(x,y)=-1$。

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，求出

输入格式

在文件 NightBird.in 中读入。

第一行一个正整数 $n$。

第二行 $n$ 个由空格隔开的正整数，第 $i$ 个正整数表示 $a_i$。

输出格式

在文件 NightBird.out 中输出。

一行 $n$ 个由空格隔开的数，第 $i$ 个表示 $\operatorname{sgcd}(a_1,a_i)$。

样例

样例输入 #1

4
12450 1 2 450

样例输出 #1

6225 -1 1 75

样例输入 #2

8
30030 6 10 12 55 36 450 666

样例输出 #2

15015 3 5 3 11 3 15 3

数据范围

共 10 个测试点，每个测试点 10 分。