\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} из входного файла выведите в отдельной строке значение требуемой суммы.