[AdditionalFile6687.zip](file://AdditionalFile6687.zip?type=additional_file)

#6687. 「Project Euler 66」解方程

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

求方程 $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$ 不是完全平方数。