I first encountered Pell's equation when I was in 10th grade so I thought it was quite common. But alas, I cannot find a blog on Codeforces that talks about it, which makes me quite sad. So here, I will talk about it for a bit.

First, let me introduce the equation, since it would be hard to talk about it otherwise. It is the diophantine equation

where $$$n$$$ is a positive integer. Usually, we are given a positive integer $$$n$$$ and then we would be asked to find the smallest positive integer $$$x$$$ such that there exists a positive integer $$$y$$$ that satisfies the equation (or vice versa, but it doesn't matter). Usually, this minimal solution is called the fundamental solution.

It is easy to see that no fundamental solution exists whenever $$$n$$$ is a perfect square. However, it is not as easy to see that there is always a solution whenever $$$n$$$ is not a perfect square. This is true, but I will omit the proof since I haven't bothered myself to learn it. After learning this fact, you try to see if it really is true since you are quite stubborn. You probably code up some inefficient program that tries to naively find the fundamental solution for non-square $$$n$$$, only to get stymied by $$$n=61$$$ where the fundamental solution is $$$(1766319049, 226153980)$$$. So next, you would ask yourself: how do I calculate the fundamental solution efficiently?

Well, of course, you would notice that if $$$(x, y)$$$ is a solution to the Pell's equation, then $$$\dfrac{x}{y}$$$ would be a good approximation for $$$\sqrt{n}$$$. And you also know another way to find a good approximation for $$$\sqrt{n}$$$: continued fractions! You try to use this discovery to optimize your code and suddenly, $$$n=61$$$ is a piece of cake! However, as you rejoice, Erdos laughs at you from his grave since your code is still not good enough to find the answer for Erdos Problem 3 in a reasonable amount of time.

Since you can't travel all the way to Erdos' grave just to spit on it, you instead resolve to solve this problem without using OEIS. And so, you try to find some more patterns. After some experimentation, you discover that the fundamental solution is found only if you end