The first few subtasks can be solved in many ways; e.g. for ~h = 2~, the simplest way is ~(a, b) = (2g, g)~. The fourth subtask is just calculating ~R(a, b)~ for ~a, b \le 1500~; we can check that this covers all ~g, h \le 20~.

For the large subtasks, the main issue is to find solutions not larger than ~10^{18}~.

Notice that, if the problem can be solved for the given constraints, it must have a solution where few division steps occur in executing Edicul's algorithm. More precisely, the product of the numbers on the sand is a nice monovariant, which decreases by a factor of ~\frac 1 b~ in each step. Since ~b \ge h~ up to the last step, there can be at most ~5~ division steps for ~h = 200\,000~.

We can play with finitely many possibilities to find a construction similar to the following one. Let ~K~ be a positive integer such that ~h^K > q~. Construction:

$$\displaystyle \begin{align*} b &= g \left\lceil \frac{h^K}{g} \right\rceil \\ a &= hb+g \end{align*}$$

Notice that ~b = h^k\ +~ something small, such that ~g~ divides ~b~. Also, we have ~b \le a \le \max(g, h)^3 \le 10^{16}~.

It's easy to see ~\gcd(a, b) = g~. Let's prove that ~R(a, b) = h~.

We have ~\lfloor \frac a b \rfloor = h~ because ~g < h^K \le b~. Hence, ~R(a, b) = R(h, b) = R(b, h)~ since ~h \le b~.

However, ~h^{K+1} > b \ge h^K~, thus ~R(b, h)~ becomes ~R(1, h) = h~ after ~K~ steps.

The time complexity is ~\mathcal O(1)~ per test case.