题目描述

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

输入格式

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

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

输出格式

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

样例

4
2
5
7
13

3 2
9 4
8 3
649 180

数据范围与提示

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