English Problem Statement

前线的排雷蚤已经排出了全部地雷的坐标！现在只需要把这些信息发送给指挥部即可。

为了避免情报外泄，通信过程需要进行加密，为此选取了一个大质数 $p=10^9+7$，并在 $\bmod p$ 意义下定义函数 $ f：\mathbb{N}^+\to \mathbb{Z}_p$ 为积性函数当且仅当：

• $f(1)=1$ 且 $\forall n,m\geq 1$，如果 $\gcd(n,m)=1$ 则 $f(nm)\equiv f(n)f(m)\pmod p$

前线部队把地雷的信息编码成了两个积性函数 $f,g$，并计算出了他们的和 $s=(f+g)\bmod p$，然后把 $s$ 发给了指挥部。

作为通信专家蚤，你现在获取了 $s(1),s(2)\cdots s(n)$ 的值，而你的任务需要还原出一组合法的 $f$ 和 $g$，如果有多组可能的解，你需要输出 $f$ 的字典序最小的一组解。

由于反潜队的干扰，有可能接收到的 $s$ 受到破坏，使得不存在任何一组合法的解，这时你需要输出 $-1$。

• 函数 $f_1$ 字典序小于 $f_2$ 当且仅当存在 $1\leq i\leq n$ 使得 $\forall 1\leq j\leq i-1,f_1(j)=f_2(j)$ 且 $f_1(i) < f_2(i)$。

输入格式

本题有多组测试数据。

第一行输入一个整数 $T$ 表示数据组数。

对于每组数据：

第一行包含一个整数 $n$ 表示需要考虑的积性函数项数。

第二行 $n$ 个非负整数依次表示 $s(1),s(2)……s(n)$。

输出格式

共 $T$ 行，对于每组数据：

如果无解，请输出 $-1$。

否则，设字典序最小的一组解为 $f(1),f(2)……f(n)$，请你输出一行 $n$ 个整数代表 $f(1),f(2)\cdots f(n)$。

2
6
2 1 4 5 1 4
20
2 12 9 11 18 69 20 9 24 102 39 72 12 72 76 21 31 120 24 90

1 0 0 0 0 0 
1 3 2 1 10 6 18 0 16 30 0 2 0 54 20 0 0 48 0 10

样例二、三、四

见附件下载，分别符合子任务 $2,7,6$ 的限制。

数据范围

对于所有数据，保证 $n\geq 1,1\leq T\leq \sum n\leq 10^6,\forall 1\leq i\leq n,0\leq s(i)\leq 10^9+6$，存在合理的子任务依赖。

特殊性质 A：保证 $s$ 为两个独立随机生成的合法积性函数的和，这里的随机指在每个素数幂的取值随机生成。

特殊性质 B：保证存在一组合法答案 $(f,g)$ 使得 $\forall 2\leq i\leq n,f(i)\neq g(i)$。

特殊性质 C：保证存在一组合法答案 $(f,g)$ 使得 $f,g$ 都是完全积性函数。

特殊性质 D：保证 $n \geq 20$。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$