A. Мадока и отец математик
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мадока наконец-то узнала пароль от своего компьютера. Но так как ее отец известный популяризатор математики, то пароль — это ответ на следующую задачу:

Требуется узнать максимальное число, сумма цифр в десятичной записи которого равна $$$n$$$, а также в его десятичной записи нет нулей и подряд идущих одинаковых цифр.

Так как Мадока уже устала от математики, то помогите ей решить эту задачу!

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке каждого набора входных данных задано число $$$n$$$ ($$$1 \le n \le 1000$$$) — необходимая сумма цифр у числа.

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

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

Пример
Входные данные
5
1
2
3
4
5
Выходные данные
1
2
21
121
212
Примечание

Все числа с суммой цифр $$$2$$$ без нулей в записи: $$$2$$$, $$$11$$$. Но последнее не подходит, так как в нем $$$2$$$ единицы подряд. Поэтому ответ $$$2$$$.

Все числа с суммой цифр $$$3$$$ без нулей в записи: $$$111$$$, $$$12$$$, $$$21$$$, $$$3$$$. Первое не подходит, так как в нём две едицины подряд, поэтому максимальное число $$$21$$$.

Все числа с суммой цифр $$$4$$$ без нулей в записи: $$$1111$$$, $$$211$$$, $$$121$$$, $$$112$$$, $$$13$$$, $$$31$$$, $$$22$$$, $$$4$$$. Числа $$$1111$$$, $$$211$$$, $$$112$$$, $$$22$$$ не подходят, так как в них есть одинаковые подряд идущих цифр. А среди остальных максимальное число — $$$121$$$.