题目描述

求解不定方程 $x^2 - D y^2 = 1$ 的最小正整数解（$x, y$ 均为正整数）。

已知 $D$ 不是完全平方数，保证方程存在正整数解。

输入格式

• 第一行：一个整数 $T$，表示测试数据组数。
• 接下来 $T$ 行：每行一个整数 $D$，表示对应测试用例的方程参数。

输出格式

对于每组测试数据，输出一行两个整数 $x$ 和 $y$（空格分隔），表示方程 $x^2 - D y^2 = 1$ 的最小正整数解。

样例

输入

4
2
5
7
13

输出

3 2
9 4
8 3
649 180

数据范围与提示

• 限制条件：$1 \leq T \leq 100$，$2 \leq D \leq 1000$，且 $D$ 不是完全平方数。
• 核心考点：佩尔方程（Pell Equation）的最小正整数解求解，通常通过连分数展开法实现。