EQU2 - Yet Another Equation

Consider the equation

x2 - ny2 = 1

where n is some integer.

Find the smallest strictly positive integer solutions (x, y) for a given n.

Input

The number of test cases t (around 30), followed by a list of t values of n (2 ≤ n ≤ 1000). You can assume that the equation can be solved for all values of n in the input set.

Output

For every test case, the values of x and y separated by a space character, on separate lines.

Example

Input:
3
2
6
61

Output:
3 2
5 2
1766319049 226153980

Added by:Mauro Persano
Date:2007-08-18
Time limit:4.739s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Brahmagupta, circa 628 AD

hide comments
2013-03-22 07:03:35 akash kumar
what if for a given value of n there exist more then one solution ...for example for n=6 ...another solution is 49 , 20
any suggestion for what to do in such cases
--ans(francky)--> Description is clear about that : print the smallest!

Last edit: 2013-03-22 07:46:22
2012-11-14 07:11:27 Aditya Pande
plz tell why my submission id 8063298 gets WA
edit: nevermind got AC

Last edit: 2012-11-22 13:14:21
2012-11-11 16:15:18 Francky
You can consider try after : http://www.spoj.pl/problems/PELL2/
with more serious constraints.
2012-02-25 04:14:36 Justin Roberts
Ugh, I keep getting NZEC with Python 2.5 here. I even tried my code with 3.1, same thing. My code works on my machine and on ideone (with the example input, obviously). Heck, on ideone, I modified it to calculate ALL solutions between 2 and 1000 in 0.46s. So frustrating knowing I have the right answer but that it is not accepted!
2010-06-30 20:34:38 suteerth
Pell's equation
2009-03-25 19:18:36 Mauro Persano
This problem requires big integers (not even 64 bits will do). I should have made it clear in the problem statement - sorry for this.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.