B. Капитан Флинт и дальнее плаванье
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вот уже несколько месяцев Капитан Флинт и его матросы держат курс к диким берегам Байтляндии, вечерами вдоволь напиваясь ромом и болтая о том о сём. В такие моменты дядя Богдан часто вспоминает своего одаренного племянника Дениса. Сегодня он поведал историю о том, как мальчик помог придумать очень интересную задачу, и предложил команде справиться с ней.

Сначала, Дядя Богдан записал на доске целое положительное десятичное число $$$x$$$ длины $$$n$$$. Потом, немного подумав, стер $$$x$$$ и написал число $$$k$$$, образованное путем конкатенации двоичных записей цифр числа $$$x$$$ (без ведущих нулей). Например, пусть $$$x = 729$$$, тогда $$$k = 111101001$$$ (так как $$$7 = 111$$$, $$$2 = 10$$$, $$$9 = 1001$$$).

Через некоторое время дядя Богдан понял, что не знает, что делать с $$$k$$$ дальше и позвал на помощь Дениса. Денис, недолго думая, стер последние $$$n$$$ цифр числа $$$k$$$ и назвал полученное число $$$r$$$.

В результате, Денис предложил искать такое число $$$x$$$ длины $$$n$$$, что полученное $$$r$$$ (как число) максимально возможное. Если же подходящих $$$x$$$ несколько, то Дениса интересует только минимальное из них.

Все члены команды, в том числе капитан Флинт, успешно справились с задачей. Все, кроме юного матроса Кости, который перебрал с выпивкой и был уже не в том состоянии. А Вы в состоянии сегодня решить эту задачу?

Уточнение: в данной задаче, мы сравниваем числа ($$$x$$$ или $$$k$$$) как числа (независимо от того, в какой системе счисления они записаны), поэтому $$$729 < 1999$$$ или $$$111 < 1000$$$.

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

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

В следующих $$$t$$$ строках заданы сами наборы — по одному в строке. В единственной строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина числа $$$x$$$, записаного дядей Богданом.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
2
1
3
Выходные данные
8
998
Примечание

Во втором наборе входных данных (с $$$n = 3$$$), если дядя Богдан записал $$$x = 998$$$, то $$$k = 100110011000$$$. Денис же (удалением последних $$$n = 3$$$ цифр) получит $$$r = 100110011$$$.

Можно доказать, что $$$100110011$$$ — максимально возможное число $$$r$$$, которое может получить Денис, и $$$998$$$ — минимальный $$$x$$$, из которого его можно получить.