题目描述

对于给定的满足 $4|x-1$ 的质数 $x$，请构造 $a,b$ 使 $x=a^2+b^2$。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行每行一个 $x$。

输出格式

对于每组数据，输出一行两个用空格分隔的非负整数 $a \leq b$，使得 $x=a^2+b^2$。

如果无解，输出一行 $QAQ$。如果有多解，输出任意一个即可。

5
5
666623333
998244353
2601257387821
999999999999999989

1 2
16598 19777
3943 31348
355005 1573286
260483990 965478167

数据范围与提示

对于50%的数据，$x \leq 10^9$。

对于100%的数据，$1 \leq T \leq 10^3$，$1 \leq x \leq 10^{18}$。