Background

锐神最近在学数论。

Description

锐神得到了一个正整数 $x$。 他想找到两个素数$p$和$q$，使得 $x=p^2*q$。

帮助锐神完成这个任务吧。

题目保证一定存在一个唯一的（$p,q$)。

Input

第一行一个正整数 T (1$\le$T$\le$10)，表示测试组数。 接下来T组测试数据，每组测试数据描述如下：

 一个正整数$x(1 \le x \le 10^{18})$，

Output

对于每个测试数据，输出两个正整数$p$和$q$，以一个空格相隔。

Samples

3
2023
63
1059872604593911

17 7
3 7
104149 97711