Мінімальна сума цифр#2437
Нехай — фіксоване натуральне число. Для r \in \{0, 1, \ldots, n - 1\} позначимо через s_{\min}(n, r) найменшу суму цифр, яку може мати число виду k n + r, де — довільне ціле невід'ємне число, а через f_{\min}(n, r) — найменше число виду k n + r, яке має суму цифр s_{\min}(n, r). Наприклад, s_{\min}(4, 3) = 2, а f_{\min}(4, 3) = 11; s_{\min}(6, 4) = 1, а f_{\min}(6, 4) = 10.
Потрібно знайти наступну суму:
де p = 10^9 + 7.
У першому рядку вхідного файлу задано натуральне число T \leq 1500, кількість тестів. У кожному з наступних рядків задано натуральне число n \leq 10^6. Сума усіх у вхідному файлі не перевищує 10^6.
Для кожного числа з вхідного файлу виведіть у окремому рядку значення потрібної суми.
Приклад 1