题目描述

给你一个整数 $x$，求出最小的 $y$，使 $x*y$ 是完全平方数。

输入格式

第一行一个整数 $n$，代表测试数据的组数（不超过 $100$）。 接下来每行一个需要被判断的正整数。（不超过$10^{14}$）

输出格式

对每个 $x$，输出最小的 $y$。

4
88
717
666
99999999999973

22
717
74
99999999999973