题目内容

给你一个正整数 $n$，请你找出 $n$ 的所有因子里，形如 $p^2$ 的因子，其中 $p$ 是质数。换句话说，$p^2$ 必须整除 $n$，并且 $p$ 必须是质数。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 $T$ ($1 \le T \le 300$) 表示数据组数，此后对于每一组测试数据： 输入一个整数 $n$ ($1 \le n \le 10^{18}$).

输出描述

对于每一组测试数据，新起一行，按照从小到大的顺序输出所有满足条件的因子 $p^2$，数与数之间用一个空格隔开。

如果不存在任何这样的因子，输出 $-1$。

样例1

输入

4
12
18
72
1000006000009

输出

4
9
4 9
1000006000009

说明

• 当 $n=12$ 时，$12 = 2^2 \cdot 3$，只有 $2^2=4$ 是质数平方因子，输出为 $4$。
• 当 $n=72$ 时，$72 = 2^3 \cdot 3^2$，满足条件的因子有 $2^2=4$ 和 $3^2=9$，按从小到大输出为 $4\ 9$。