[Poi2012]Distance

时间限制:40s      空间限制:128MB

题目描述


对于两个正整数a、b,这样定义函数d(a,b):每次操作可以选择一个质数p,将a变成a*p或a/p,

如果选择变成a/p就要保证p是a的约数,d(a,b)表示将a变成b所需的最少操作次数。例如d(69,42)=3。

现在给出n个正整数A1,A2,...,An,对于每个i (1<=i<=n),求最小的j(1<=j<=n)使得i≠j且d(Ai,Aj)最小。




输入格式

第一行一个正整数n (2<=n<=100,000)。第二行n个正整数A1,A2,...,An (Ai<=1,000,000)。




输出格式

输出n行,依次表示答案。




样例输入

6
1
2
3
4
5
6


样例输出

2
1
1
2
1
2

提示

没有写明提示


题目来源

鸣谢 oimaster