题目内容

在整数理论中，定义一类特殊的正整数，称为基源数：一个大于 1 的正整数，如果除了 1 和它本身之外没有其他正约数，则称它为基源数。对于任意正整数 $N$，若存在基源数 $k$，使得 $k^2$ 整除 $N$，则称 $k^2$ 为 $N$ 的一个基方因子。 给定 $T$ 个询问，每个询问给出一个正整数 $N$。对于每个询问，请找出 $N$ 的所有基方因子，并按升序输出。如果 $N$ 不存在任何基方因子，则输出 -1。 本题中，询问组数 $T$ 不超过 300，每个 $N$ 的大小不超过 10^{18}。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 300$），表示询问组数。 接下来 $T$ 行，每行包含一个整数 $N$（$1 \le N \le 10^{18}$），表示一次询问。

输出描述

对于每组询问输出一行：若存在基方因子，将它们按升序输出，相邻整数用一个空格隔开；否则输出 -1。

样例1

输入

1
36

输出

4 9

说明

$36 = 2^2 \times 3^2$。基源数 2 出现 2 次，$2^2 = 4$ 是基方因子；基源数 3 出现 2 次，$3^2 = 9$ 是基方因子。按升序输出 $4$ 和 $9$。

样例2

输入

1
20402

输出

10201

说明

$20402 = 2 \times 101^2$。基源数 2 仅出现 1 次，不产生基方因子；基源数 101 出现 2 次，$101^2 = 10201$ 是基方因子。无其他基方因子，输出 $10201$。

样例3

输入

2
1
12

输出

-1
4

说明

第一个询问 $N = 1$：不存在基方因子，输出 $-1$。 第二个询问 $N = 12 = 2^2 \times 3$：基源数 2 出现 2 次，$2^2 = 4$ 是基方因子；基源数 3 仅出现 1 次，无基方因子。输出 $4$。