\includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} Нехай \textbf{n} - фіксоване натуральне число. Для \textbf{r} \textbf{\{0, 1, ..., n-1\}} позначимо через \textbf{s_min(n, r)} найменшу суму цифр, яку може мати число виду \textbf{kn+r}, де \textbf{k} - довільне ціле невід'ємне число, а через \textbf{f_min(n, r)} - найменше число виду \textbf{kn+r}, яке має суму цифр \textbf{s_min(n, r)}. Наприклад, \textbf{s_min(4, 3)=2}, а \textbf{f_min(4, 3)=11}; \textbf{s_min(6, 4)=1}, а \textbf{f_min(6, 4)=10}. Потрібно знайти наступну суму \includegraphics{https://static.e-olymp.com/content/66/66a7a8e66558100e4c91c9a9079ae9d36b60ca2f.jpg} де \textbf{p = 10^9 + 7}. \InputFile У першому рядку вхідного файлу задано натуральне число \textbf{T} ≤ \textbf{1500}, кількість тестів. У кожному з наступних \textbf{T} рядків задано натуральне число \textbf{n} ≤ \textbf{10^6}. Сума усіх \textbf{n} у вхідному файлі не перевищує \textbf{10^6}. \OutputFile Для кожного числа \textbf{n} з вхідного файлу виведіть у окремому рядку значення потібної суми.