Minimum sum of digits
Let n be a fixed natural number. For each r in the set {0, 1, ..., n-1}, define s_min(n, r) as the smallest possible sum of digits for a number of the form kn+r, where k is any non-negative integer. Additionally, define f_min(n, r) as the smallest number of the form kn+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.
Input
The first line of the input file contains a natural number T ≤ 1500, representing the number of test cases. Each of the following T lines contains a natural number n ≤ 10^6. The total sum of all n values in the input file does not exceed 10^6.
Output
For each n provided in the input file, output the calculated sum on a separate line.