Sequence with Digits
Contest: Codeforces Round 643 (Div. 2)
Difficulty rating: 1200
Tags: brute force, implementation, math

Let's define the following recurrence: $$$$$$a_{n+1} = a_{n} + minDigit(a_{n}) \cdot maxDigit(a_{n}).$$$$$$

Here $$$minDigit(x)$$$ and $$$maxDigit(x)$$$ are the minimal and maximal digits in the decimal representation of $$$x$$$ without leading zeroes. For examples refer to notes.

Your task is calculate $$$a_{K}$$$ for given $$$a_{1}$$$ and $$$K$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of independent test cases.

Each test case consists of a single line containing two integers $$$a_{1}$$$ and $$$K$$$ ($$$1 \le a_{1} \le 10^{18}$$$, $$$1 \le K \le 10^{16}$$$) separated by a space.

Output format:
For each test case print one integer $$$a_{K}$$$ on a separate line.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
$$$a_{1} = 487$$$

$$$a_{2} = a_{1} + minDigit(a_{1}) \cdot maxDigit(a_{1}) = 487 + \min (4, 8, 7) \cdot \max (4, 8, 7) = 487 + 4 \cdot 8 = 519$$$

$$$a_{3} = a_{2} + minDigit(a_{2}) \cdot maxDigit(a_{2}) = 519 + \min (5, 1, 9) \cdot \max (5, 1, 9) = 519 + 1 \cdot 9 = 528$$$

$$$a_{4} = a_{3} + minDigit(a_{3}) \cdot maxDigit(a_{3}) = 528 + \min (5, 2, 8) \cdot \max (5, 2, 8) = 528 + 2 \cdot 8 = 544$$$

$$$a_{5} = a_{4} + minDigit(a_{4}) \cdot maxDigit(a_{4}) = 544 + \min (5, 4, 4) \cdot \max (5, 4, 4) = 544 + 4 \cdot 5 = 564$$$

$$$a_{6} = a_{5} + minDigit(a_{5}) \cdot maxDigit(a_{5}) = 564 + \min (5, 6, 4) \cdot \max (5, 6, 4) = 564 + 4 \cdot 6 = 588$$$

$$$a_{7} = a_{6} + minDigit(a_{6}) \cdot maxDigit(a_{6}) = 588 + \min (5, 8, 8) \cdot \max (5, 8, 8) = 588 + 5 \cdot 8 = 628$$$

Example input:
8
1 4
487 1
487 2
487 3
487 4
487 5
487 6
487 7

Example output:
42
487
519
528
544
564
588
628

Editorial:
Let's calculate the sequence for fixed $$$a_{1} = 1$$$: $$$1, 2, 6, 42, 50, 50, 50, \ldots$$$
We got lucky and the minimal digit has become 0, after that the element has stopped changing because we always add 0.
Actually it is not luck and that will always happen. Note that we add no more than $$$9 \cdot 9 = 81$$$ every time, so the difference between two consecutive elements of the sequence is bounded by 81. Assume that we will never have minimal digit equal to 0. Then the sequence will go to infinity. Let's take $$$X = 1000(\lfloor \frac{a_{1}}{1000} \rfloor + 1)$$$. All the numbers on segment $$$[X;X+99]$$$ have 0 in hundreds digit, so none of them can be element of our sequence. But our sequence should have numbers greater than $$$X$$$. Let's take the smallest of them, it should be at least $$$X + 100$$$. But then the previous number in the sequence is at least $$$(X + 100) - 81 = X + 19$$$. It is greater than $$$X$$$ but smaller than the minimal of such numbers. Contradiction.
In the previous paragraph we have actually shown that we have no numbers greater than $$$X + 100$$$ in our sequence and we will see the number with 0 among first 1001 elements.
That means that we can build the sequence till we find the first number with 0 and then it will repeat forever.
In reality the maximal index of the first elements with 0 is 54 and minimal $$$a_{1}$$$ for that to happen is 28217.