Start with a positive integer \(n\).
Repeatedly, take the first digit of your current number and subtract it from the number.
Eventually, you’ll reach zero. Count the steps until that happens.
Report that count modulo \(10^9 + 7\) (to keep the output small).
The first line of each input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.
Each test case consists of a single line containing one value of \(n\).
For each test case output a single line with one integer: the value \((x \bmod 1\,000\,000\,007)\), where \(x\) is the number of steps needed to get from \(n\) to \(0\).
Input file: S1.in
Constraints: \(t = 100\) and each \(n\) has at most 7 digits.
Input file: S2.in
Constraints: \(t = 100\) and each \(n\) has at most 18 digits.
Input file: S3.in
Constraints: \(t = 100\) and each \(n\) has exactly \(20\,000\) digits.
input4 8 17 37 1234567 | output1 9 18 548891 |
The example input contains \(t=4\) test cases: \(n=8\), \(n=17\), \(n=37\), and \(n=1\,234\,567\).
For \(n=8\) we subtract 8 from 8 and get 0, so we are done in a single step.
For \(n=17\) the process looks as follows: 17 → 16 → 15 → 14 → 13 → 12 → 11 → 10 → 9 → 0.
For \(n=37\) the following will happen: 37 → 34 → 31 → 28 → 26 → 24 → 22 → 20 → 18 → 17 → 16 → 15 → 14 → 13 → 12 → 11 → 10 → 9 → 0.
input1 4567890123 | output289635647 |
The second example contains a single test case with \(n=4\,567\,890\,123\). Note that this \(n\) is bigger than the constraint for subproblem S1, but it could appear in subproblem S2.
For this \(n\), the total number of steps is \(x = 2\,289\,635\,661\), so the correct output is the remainder this \(x\) gives when divided by \(10^9 + 7\).
