Assume two integers $$$a$$$ and $$$b$$$ ($$$1 \le b < a$$$) that form an ordered integer pair $$$(a, b)$$$. We can perform a Euclidean division on it, which will make it $$$(b, a \bmod b)$$$. If we keep performing this division, then $$$b$$$ will eventually be $$$0$$$. We define $$$k$$$ as the number of Euclidean divisions needed to make $$$b$$$ equal $$$0$$$.
Example: $$$(19, 8)$$$ → $$$(8, 3)$$$ → $$$(3, 2)$$$ → $$$(2, 1)$$$ → $$$(1, 0)$$$. We perform $$$4$$$ divisions until $$$b$$$ equals $$$0$$$, so $$$k = 4$$$.
With the value of $$$k$$$ specified ($$$1 \le k \le 10^9$$$), how to find any ordered integer pair $$$(a, b)$$$ ($$$1 \le b < a \le 10^{18}$$$) that needs exactly $$$k$$$ Euclidean division to make $$$b$$$ equal $$$0$$$? If there does not exist such a pair, report it.
I am also curious about one question: it is all known that the Euclidean algorithm is fast, but the speed of the algorithm is determined by $$$k$$$, so may $$$k$$$ be infinitely large?