SPOJ.com - Problem EQU2

EQU2 - Yet Another Equation

no tags

Consider the equation

x² - ny² = 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

Submit solution!

hide comments



	akash kumar: 2013-03-22 07:03:35 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
	Aditya Pande: 2012-11-14 07:11:27 plz tell why my submission id 8063298 gets WA edit: nevermind got AC Last edit: 2012-11-22 13:14:21
	Francky: 2012-11-11 16:15:18 You can consider try after : http://www.spoj.pl/problems/PELL2/ with more serious constraints.
	Justin Roberts: 2012-02-25 04:14:36 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!
	suteerth: 2010-06-30 20:34:38 Pell's equation
	Mauro Persano: 2009-03-25 19:18:36 This problem requires big integers (not even 64 bits will do). I should have made it clear in the problem statement - sorry for this.

Submit solution!

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