2067C.md (1744B)
1 Source: https://codeforces.com/problemset/problem/2067/C 2 3 C. Devyatkino 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 What is the minimum number of operations needed to make the number $n$ contain at least one digit $7$ in its decimal representation? 24 25 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$. 26 27 Input 28 29 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. 30 31 The only line of each test case contains an integer $n$ ($10 \leq n \leq 10^9$). 32 33 Output 34 35 For each test case, output the minimum number of operations required for the number $n$ to contain the digit $7$. 36 37 Example 38 39 Input 40 41 ``` 42 16 43 44 51 45 46 60 47 48 61 49 50 777 51 52 12345689 53 54 1000000000 55 56 2002 57 58 3001 59 60 977 61 62 989898986 63 64 80 65 66 800001 67 68 96 69 70 70 71 72 15 73 74 90 75 ``` 76 77 Output 78 79 ``` 80 3 81 2 82 1 83 0 84 1 85 3 86 5 87 4 88 0 89 7 90 1 91 2 92 7 93 0 94 7 95 3 96 ``` 97 98 Note 99 100 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. 101 102 In the second test case, two operations are sufficient: $60 + 9 + 9 = 78$. 103 104 In the third test case, one operation is sufficient: $61 + 9 = 70$. 105 106 In the fourth test case, $n$ already contains the digit $7$, so no operations are required. 107 108 In the fifth test case, you can add $99$ to $n$ to obtain a number containing the digit $7$.