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

Нехай 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 з вхідного файлу виведіть у окремому рядку значення потібної суми.

Приклади