eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Минимальная сумма цифр

Минимальная сумма цифр

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

Пусть n - фиксированное натуральное число. Для r{0, 1, ..., n-1} обозначим через s_min(n, r) наименьшую сумму цифр, которую может иметь число вида kn+r, где k - произвольное целое неотрицательное число, а через f_min(n, r) - наименьшее число вида kn+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.

Входные данные

В первой строке входного файла задано натуральное число T1500, количество тестов. В каждой из последующих T строк задано натуральное число n10^6. Сумма всех n во входном файле не превосходит 10^6.

Выходные данные

Для каждого числа n из входного файла выведите в отдельной строке значение требуемой суммы.

Пример

Входные данные #1
6
1
2
3
4
5
6
Выходные данные #1
0
1
3
22
10
27