解方程

题目描述

求方程 x^2-Dy^2=1 的最小正整数解。

输入

第一行一个整数 T ,代表数据组数。

接下来 T 行,每行一个整数 D ,保证 D 不是完全平方数。

输出

T 行,每行两个整数 x、y ,用空格分隔。

样例

提示

1 \leq T \leq 100, 2 \leq D \leq 100，保证D不是完全平方数。