问题描述

小瓜在新年之际参加了一个数学挑战活动，主办方给了她 $n$ 个神秘的纸条，每个纸条上都写着一个整数。其中每个数都有一个特别的性质：它可以表示为 $p^2q$ 的形式，其中 $p$ 和 $q$ 是两个不同的素数。只要能把这些数成功分解，就算挑战成功。你能帮小瓜解决这些新年谜题，找到每个 $a_i$ 对应的 $p$ 和 $q$ 吗？

输入格式

第一行：一个整数 $n$，表示纸条的数量。

接下来 $n$ 行：每行一个整数 $a_i$，分别表示每个纸条上写的数字。

输出格式

输出 $n$ 行，每行包含两个整数 $p,q$，表示当前的数可以分解为 $p^2q$。

2
2023
63

17 7
3 7

数据范围

对于 $40\%$ 的数据，$1≤n≤10，1≤a_i≤1000$。

对于 $60\%$ 的数据，$1≤n≤10，1≤a_i≤10^9$。

对于 $100\%$ 的数据，$1≤n≤10，1≤a_i≤10^{18}$。