题目描述

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

输入格式

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

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

输出格式

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

样例

input

4
2
5
7
13

output

3 2
9 4
8 3
649 180

数据范围与提示

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