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

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

Каждую секунду цифры на всех панелях увеличиваются на $$$1$$$. Другими словами, по прошествии каждой секунды панель, которая показывала $$$9$$$, станет показывать $$$0$$$; панель, которая показывала $$$0$$$, станет показывать $$$1$$$; панель, которая показывала $$$1$$$, станет показывать $$$2$$$ и так далее.

Если панель остановить, то цифра, отображаемая на этой панели, не будет меняться в последующие секунды.

Необходимо остановить ровно одну панель в любую секунду. После этого панели, примыкающие к ней, будут остановлены через одну секунду; панели, примыкающие к этим, будут остановлены через $$$2$$$ секунды и так далее. Иными словами, если остановить панель $$$x$$$, то панель $$$y$$$ (для любых возможных $$$y$$$) будет остановлена ровно через $$$|x−y|$$$ секунд.

Например, если есть $$$4$$$ панели, и мы останавливаем $$$3$$$-ю панель, когда на ней отображается цифра $$$9$$$, происходит следующее:

  • панель $$$1$$$ останавливается через $$$2$$$ секунды, когда на ней отображается цифра $$$1$$$;
  • панель $$$2$$$ останавливается через $$$1$$$ секунду, когда на ней отображается цифра $$$0$$$;
  • панель $$$4$$$ останавливается через $$$1$$$ секунду, когда на ней отображается цифра $$$0$$$.

Получается число из $$$4$$$ цифр: $$$1090$$$. Обратите внимание: этот пример не является оптимальным ответом для $$$n = 4$$$.

Как только все панели остановлены, все отображенные на них цифры выписываются слева направо, составляя число из $$$n$$$ разрядов (в нем могут встречаться ведущие нули). Какое самое большое число при этом может быть получено? Изначально все панели показывают $$$0$$$.

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

Первая строка входных данных состоит из единственного целого числа $$$t$$$ ($$$1 \le t \le 100$$$) — количества наборов входных данных. Каждый такой набор состоит из одной строки, содержащей единственное целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$).

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

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

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

Пример
Входные данные
2
1
2
Выходные данные
9
98
Примечание

Для первого набора входных данных оптимальным будет остановить первую панель, когда на ней отображается цифра $$$9$$$.

Для второго набора входных данных оптимальным будет остановить вторую панель, когда на ней отображается цифра $$$8$$$.