eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 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.

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
6
1
2
3
4
5
6
Çıxış verilənləri #1
0
1
3
22
10
27