计算质因数

题目描述

小珅非常喜欢研究数学问题，这天他学习了质因数的定义，觉得很有意思。他想：每个大于 1 的数 x 都会有若干个质因数，如果把 x 的质因数乘起来，会有什么规律和特殊的性质吗？他把这个乘积定义为“因质数”，决定深入研究一下。那第一步就是先把每个数的“因质数”求出来。

现在给出 N 个正整数，求出每个数的因质数是多少。相同的质因数只在乘积中计算一次，例如 56 的质因数有 2、7，因质数为 2×7=14。

输入描述

第一行一个正整数 N，表示数的个数。

第二行 N 个正整数 $X_1$、$X_2$、……、$X_N$。

输出描述

一行用空格隔开的 N 个正整数，分别表示 $X_1$、$X_2$、……、$X_N$ 的因质数。

样例 1

输入：

2
8 13

输出：

2 13

样例 2

输入：

3
56 18 45

输出：

14 6 15

样例 3

输入：

4
70 150 164 155

输出：

70 30 82 155

数据范围

• 对于 30% 的数据：1 ≤ N ≤ 10^3，1 ≤ $X_i$ ≤ 100。
• 对于 60% 的数据：1 ≤ N ≤ 10^4，1 ≤ $X_i$ ≤ 10^3。
• 对于 100% 的数据：1 ≤ N ≤ 10^6，1 ≤ $X_i$ ≤ 10^6。