「Wdoi-1」加密通信

自月战之后，八云紫在槐安通道中设立了一重结界，使得从地面传向月都的信息全部会被拦截和破译。 为了维持正常的通讯，八意永琳同月兔们研究出了一种全新的加密方式。

首先，八意永琳会写出需要被加密的明文 $A$ ，此段明文由 $n-1$ 个正整数构成。 之后，她会构造出一个由 $n$ 个**质数**构成的密文 $B$，满足对 $\forall i \in [1,n),B_i \times B_{i + 1} = A_i$。 为了提高信息的利用率，八意永琳规定 $B$ 中出现的所有质数的值必须在 $[1,M]$ 范围内。

第一行一个整数 $T$ , 表示需要被加密的明文的组数。 对于每组明文： 第一行两个整数 $n,M$ ，代表明文的长度$+1$，也即所求密文的长度和可出现质数的最大值。 接下来一行 $n - 1$ 个由空格隔开的正整数，代表明文 $A$。

对于每组明文，均输出一行： - 若有解，输出**任意一组**合法密文 $B$ 即可，密文中的 $n$ 个质数以空格隔开。 - 若无解，输出 `-1`。

2
4 233
55 35 77
4 5
55 35 77 

11 5 7 11 
-1

#### 数据规模 - 对于 $20\%$ 的数据，$n \le 5,M \le 10$。 - 对于 $40\%$ 的数据，$A_i \le 10 ^ {12}$。 - 对于 $70\%$ 的数据， $A_i \neq A_{i + 1}$。 - 对于$100\%$的数据，$3 \le n \le 10 ^ 5$，$1 \le A_i,M \le 10 ^ {18}$，$1 \le T \le 5$。 - 以上几档部分分呈**包含关系**，$100\%$ 包含 $70\%$，$70\%$ 包含 $40\%\ \ldots\ldots$以此类推。 #### 数据保证： - 若不考虑 $b_i$ 在 $[1,M]$ 范围内的条件，必然有至少一组合法解。 - 有至少一对 $(i,j)$，使得 $A_i \neq A_j$。 #### 后置资料 **本段资料与答题相关性不大**。 [百度百科 - 质数](https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0/263515?fr=aladdin)