Minimum sum of digits#2437
Let be a fixed natural number. For each in the set \{0, 1, \ldots, n - 1\}, define s_{\min}(n, r) as the smallest possible sum of digits for a number of the form k n + r, where is any non-negative integer. Additionally, define f_{\min}(n, r) as the smallest number of the form k n + r that has the digit sum s_{\min}(n, r). For instance, s_{\min}(4, 3) = 2 and f_{\min}(4, 3) = 11; similarly, s_{\min}(6, 4) = 1 and f_{\min}(6, 4) = 10.
Your task is to calculate the following sum:
where p = 10^9 + 7.
The first line of the input file contains a natural number T \leq 1500, representing the number of test cases. Each of the following lines contains a natural number n \leq 10^6. The total sum of all values in the input file does not exceed 10^6.
For each provided in the input file, output the calculated sum on a separate line.
Example 1