大学霸KK 在学习了不定方程的有关知识后被布置了一堆有关于不定方程求解的作业。
KK当然没有这么多时间来做这些对于他来说水的不对的题目，于是他打算编一个程序来搞定这些作业。
因此KK的老师非常的Nice，所以他布置的题目都为同一类型。题目如下：
对于方程x^2-d*y^2=1，给定一个数d（非完全平方数），求出最小的正整数解（x,y）,使等式成立。（优先x最小，然后y要最小）
测试数据中第一行为一个数字T，代表接下来有T组测试数据(0<=T<=1000)
接下来T行，每行给出一个数字D (0<=D<=1e9)
每个测试样例输出一行，即x，y的值
数据保证1<=x,y<=1e9;保证一定有解。