Description

XMU的CYH即将退役，他为了培养下一代大神LYH接他的班，给他出了一道题目

对于一个正整数x，给出两种操作：选择一个质数p，使x变成x/p或x*p。其中若使用的是除法操作，则p必须是x的质因数。定义函数D(x, y)表示从x变到y所需要的最小操作次数。
现在给你一个长度为n的序列A_1,A_2,…,A_n, 对于每个i，求出使D(A_i,A_j)最小的j。若有多个答案，输出最小的那个。

你觉得你也能像LYH一样优秀，所以你打算和LYH同时尝试着解这道题

Format

Input

第一行一个正整数n (2<=n<=100,000)。第二行n个正整数A_1,A_2,…,A_n, (A_i≤1000000)。

Output

输出n行，第i行表示A_i对应的答案。

Sample 1

Input

6
1
2
3
4
5
6

Output

2
1
1
2
1
2 

Limitation

1s, 128MB for each test case.

Hint

Source

CYH