Devyatkino
Contest: Codeforces Round 1004 (Div. 2)
Difficulty rating: 1500
Tags: brute force, dfs and similar, greedy, math

You are given a positive integer $$$n$$$. In one operation, you can add to $$$n$$$ any positive integer whose decimal representation contains only the digit $$$9$$$, possibly repeated several times.

What is the minimum number of operations needed to make the number $$$n$$$ contain at least one digit $$$7$$$ in its decimal representation?

For example, if $$$n = 80$$$, it is sufficient to perform one operation: you can add $$$99$$$ to $$$n$$$, after the operation $$$n = 179$$$, which contains the digit $$$7$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains an integer $$$n$$$ ($$$10 \leq n \leq 10^9$$$).

Output format:
For each test case, output the minimum number of operations required for the number $$$n$$$ to contain the digit $$$7$$$.

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

Note:
In the first test case, three operations are sufficient: $$$51 + 9 + 9 + 9 = 78$$$, which contains the digit $$$7$$$. It can be shown that it is impossible to achieve the goal in one or two operations.

In the second test case, two operations are sufficient: $$$60 + 9 + 9 = 78$$$.

In the third test case, one operation is sufficient: $$$61 + 9 = 70$$$.

In the fourth test case, $$$n$$$ already contains the digit $$$7$$$, so no operations are required.

In the fifth test case, you can add $$$99$$$ to $$$n$$$ to obtain a number containing the digit $$$7$$$.

Example input:
16
51
60
61
777
12345689
1000000000
2002
3001
977
989898986
80
800001
96
70
15
90

Example output:
3
2
1
0
1
3
5
4
0
7
1
2
7
0
7
3

Editorial:
The first idea: the answer does not exceed $$$9$$$, since we can add $$$9$$$ and keep track of the last digit; with each addition, it will decrease by $$$1$$$ (going from $$$0$$$ to $$$9$$$), so after $$$9$$$ additions, the last digit will complete a full cycle and will be $$$7$$$ exactly once during the process.
The second idea: it is quite difficult to briefly answer how adding a number like $$$99..99$$$ will affect the digits of an arbitrary number. However, there is an arithmetically similar operation, adding a number of the form $$$10^x$$$, which affects the digits in a much more predictable way. It would be nice if we could add powers of ten in the operation instead of $$$99..99$$$.
The combination of these two ideas solves the problem.
Let's iterate through the possible values of the answer. For each $$$k$$$ from $$$0$$$ to $$$9$$$, we want to determine: is it possible to add exactly $$$k$$$ numbers made up of nines to produce a digit $$$7$$$? One operation is adding a number of the form $$$10^x - 1$$$. Since we know we will perform exactly $$$k$$$ operations, we can view this process as adding $$$k$$$ powers of ten to the number $$$n-k$$$.
Adding a power of ten increases one of the digits of the number by $$$1$$$ (including leading zeros). It may also replace some $$$9$$$s with $$$0$$$s, which effectively is also an increase of the digit by $$$1$$$, modulo $$$10$$$. Therefore, it is not difficult to understand that the minimum number of additions of powers of ten needed to introduce a digit $$$7$$$ into the number is $$$\min((7 - digit) \bmod 10)$$$ across all digits $$$digit$$$ from the number, including leading zeros.
In summary, we need to iterate $$$k$$$ from $$$0$$$ to $$$9$$$ and compare $$$k$$$ with $$$\min((7 - digit) \bmod 10)$$$ (where $$$digit$$$ is any digit from the number $$$n-k$$$, including leading zeros), and output the minimum suitable $$$k$$$.
From interesting facts: during the solution process, it becomes clear that the answer is $$$\leq 7$$$, since $$$digit$$$ can always be $$$0$$$. However, this is only true under the constraints $$$n \geq 7$$$, as in the solution we implicitly rely on the fact that the number $$$n-k$$$ does not go negative! For $$$n=5$$$ and $$$n=6$$$, the answer is actually $$$8$$$.
Additionally, the solution presented above serves as a proof of another solution that one could believe with sufficient intuition. Let's say that in the optimal answer we add the same number, meaning we never mix adding $$$9$$$ and $$$99$$$. Believing this, we can iterate through the number being added and keep adding it until we encounter the digit $$$7$$$. We then take the minimum of all options for the answer.