PELLFOUR - Pell Fourth

The double palindrome, or Quarter Pell Art

Leo was quietly fighting with XerK along the East-coast with 300 friends, when XerK proposed Leo a beer, it was a Pell-Fourth.
Then XerK told Leo he had a good problem found in an ancient book :

--
D is a given positive integer, consider the equation :
X² = D×Y² + 1, with X and Y positive integers.
Find the minimum number X within all solutions.
Sometimes it's possible, sometimes not!

Examples :
If D=2, 3² = 2×2² + 1, so X=3.
If D=3, 2² = 3×1² + 1, so X=2.
If D=4, it's impossible!
--

Leo said that he very well knows this problem and claimed that there is yet on SPOJ a classic edition and surely others related ones. But XerK told him he had an army of byteland's computer that gave him the list of the worst test cases for D. This list begins with 2, 5, 10, ...

First examples are:

 D   X
 2   3
 5   9
10  19

where each new line is the minimal D to break a new record for X.
E.g : for any D in [5, 10[, X(D) will be not greater than 9; and X(10) is greater than 9.

The search and print of those 'pell-fect' (D, X) is the goal of this challenge.

Input

There's no input for this challenge.

Output

Start with D=2 and X=3, and print consecutive 'pell-fect' "D X" of this sequence.
As the answer X could be a huge number, print instead CHK(X, 2^16384), this only affect X numbers on line 127 and after.

Example

Output:
2 3
5 9
10 19
[...]

constraints

This is madness, but XerK can judge 1000 lines. (Edit 12/II/2017 : the MasterJudge take time into account if all 1000 lines are given.)

Score

If you can output n lines, XerK decided that the fairest score was exp(sqrt(n)), but he didn't want to tell why, so it was decided to set the score at 'just' n. You need to output more than 44 lines to get accepted.


Added by:Francky
Date:2012-12-01
Time limit:44s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Extension of Project Euler n°###

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.