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

Пусть 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.

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

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

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

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

Примеры