PELL2  Pell (Mid pelling)
D is a given positive integer, consider the equation :
X² = D×Y² + 1, with X and Y positive integers.
Find the minimum numbers (X,Y) within all solutions.
Sometimes it's possible, sometimes not!
Examples :
If D=2, 3² = 2×2² + 1, so X=3 and Y=2.
If D=3, 2² = 3×1² + 1, so X=2 and Y=1.
If D=4, it's impossible!
Input
The input begins with the number T of test cases in a single line.
In each of the next T lines there is one integer D.
Output
For each test case, if possible print X and Y the answer of the problem for D, else "1".
Example
Input: 3 2 3 4 Output: 3 2 2 1 1
Constraints
T <= 1000
1 < D <= 10^7, the numbers D were randomly chosen. (but XerK modified one of them!)
190 bytes of suboptimal python code can get AC in less than 2.5 seconds, there's many rooms to make faster code.
If you have TLE, you should first consider EQU2 first.
Edit(20170211, after compiler updates) : New TL at 1.5s. The Python awaited solution ends under 0.8s, pike or java around 1.4s. Some old AC might not keep their AC : here it's midpelling. The 'mid' is to be kept in consideration.
hide comments
Prime:
20151215 05:02:37
Does the answer exceed 10^1000?


Francky:
20141222 00:29:16
Edit : I didn't merge no more the rank list. All comments set at this time, after this change. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20141222 00:27:58
@Francky: I wonder why you don't solve any problem for more than last 2.5 months?


[Lakshman]:
20141222 00:27:58
@Francky can you please suggest me if I am doing some thing wrong. Getting TLE, I tried the same code for EQU2 and got AC in just .04 seconds, Or my algorithm is slow?


Aditya Pande:
20141222 00:27:58
TLE


Ehor Nechiporenko:
20141222 00:27:58
Really nice math problem 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20141222 00:27:58
I need fast I/O to solve this, wait until I master dynamic bignum in C ;)

Added by:  Francky 
Date:  20121111 
Time limit:  1.75s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Old problem 