Пропонуємо математичну головоломку. Нехай ми маємо натуральне число ~n~. Запишемо його у перший рядок аркушу. Віднімемо від нього його першу цифру і результат запишемо у другий рядок. Якщо результат не 0, то від отриманого числа віднімемо його першу цифру і запишемо у новий рядок. Продовжуємо це робити до тих пір, поки не запишемо у рядок 0. Так ми отримали ~k~ рядків, і в ~k~-му рядку записано 0.

Наприклад, для ~n~ = 10 ми отримаємо:

• 10
• 9
• 0

Тепер таке завдання. Відомо, що на аркуші записано ~k~ рядків чисел. Вам треба знайти максимально можливе натуральне число, яке може бути записане першим у послідовності довжиною ~k~.

Input

Перший рядок містить ~T~ (~1 \le T \le 30~) - кількість тестів. Єдиний рядок кожного тесту містить одне ціле число ~k~ (~2 \le k \le 10^{12}~) - кількість чисел у послідовності

Output

Виведіть для кожного тесту в окремому рядку одне ціле число - найбільше можливе значення початкового числа ~n~. Гарантується, що принаймні одне таке число ~n~ існує та воно є скінченим.

Sample Input 1

3
3
10
100

Sample Output 1

10
17
170