有 $n$ 个数，分别是 $a_1,a_2,a_3......a_n$，定义 $sgcd(x,y)$ 为两数的次大公约数，即能同时整除$x,y$的正整数中第二大的数。求出 $sgcd(a_1,a_1),sgcd(a_1,a_2),sgcd(a_1,a_3)...sgcd(a_1,a_n)$。如果两数没有次大公约数，则输出 $-1$，比如 $3$ 和 $7$，$1$和$99$。

$n \le 10^5,a_i \le 10^{12}$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
ll n,k,a;
int gcd(ll a,ll b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
int sgcd(ll k)
{
	for(int i=2;i*i<=k;i++)
	{
		if(k%i==0)return k/i;
	}
	return 1;
}
int su(ll k)
{
	for(int i=2;i*i<=k;i++)
	{
		if(k%i==0)return 0;
	}
	return 1;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		if(i==1)
		{
			k=a;
			cout<<sgcd(k)<<" ";
			continue;
		}
		if(k==1||a==1)
		{
			cout<<"-1 ";
			continue;
		}
		if(gcd(k,a)==1&&su(k)==1&&su(a)==1)
		{
			cout<<"-1 ";
			continue;
		}
		int t=gcd(k,a);
		cout<<sgcd(t)<<" ";
	}
	return 0;
}