B. Минимизируйте единичность
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для произвольной бинарной строки $$$t$$$$$$^{\text{∗}}$$$, пусть $$$f(t)$$$ — количество непустых подпоследовательностей$$$^{\text{†}}$$$ $$$t$$$, которые содержат только символы $$$\mathtt{0}$$$, и пусть $$$g(t)$$$ — это количество непустых подпоследовательностей $$$t$$$, которые содержат хотя бы одну $$$\mathtt{1}$$$.

Обратите внимание, что для $$$f(t)$$$ и $$$g(t)$$$ каждая подпоследовательность считается столько раз, сколько раз она встречается в $$$t$$$. Например, $$$f(\mathtt{000}) = 7, g(\mathtt{100}) = 4$$$.

Назовём единичностью бинарной строки $$$t$$$ значение $$$|f(t)-g(t)|$$$, где $$$|z|$$$ обозначает абсолютное значение $$$z$$$ для любого числа $$$z$$$.

Вам дано целое положительное число $$$n$$$. Найдите бинарную строку $$$s$$$ длины $$$n$$$, такую, чтобы её единичность была как можно меньше. Если строк несколько, вы можете вывести любую из них.

$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая только из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Последовательность $$$a$$$ является подпоследовательностью последовательности $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, нуля или всех) элементов. Например, подпоследовательности $$$\mathtt{1011101}$$$ — это $$$\mathtt{0}$$$, $$$\mathtt{1}$$$, $$$\mathtt{11111}$$$, $$$\mathtt{0111}$$$, но не $$$\mathtt{000}$$$ и не $$$\mathtt{11100}$$$.

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

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

Единственная строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — длина $$$s$$$.

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

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

Для каждого набора входных данных выведите $$$s$$$ на отдельной строке. Если существует несколько ответов, выведите любой.

Пример
Входные данные
3
1
2
3
Выходные данные
0
01
010
Примечание

В первом наборе входных данных $$$f(t)=1$$$, потому что существует одна подпоследовательность, содержащая только $$$\mathtt{0}$$$ (подпоследовательность $$$\mathtt{0}$$$), и $$$g(t)=0$$$, потому что нет подпоследовательностей, содержащих хотя бы одну $$$1$$$. Единичность равна $$$|1-0|=1$$$. Строка $$$\mathtt{1}$$$ также является корректным ответом, так как её единичность равна $$$|0-1|=1$$$.

Во втором наборе входных данных $$$f(t)=1$$$, потому что существует одна непустая подпоследовательность, содержащая только $$$\mathtt{0}$$$, и $$$g(t)=2$$$, потому что существуют две непустые подпоследовательности, содержащие хотя бы одну $$$\mathtt{1}$$$ ($$$\mathtt{01}$$$ и $$$\mathtt{1}$$$). Таким образом, единичность равна $$$|1-2|=1$$$. Можно показать, что $$$1$$$ — это минимально возможное значение единичности среди всех бинарных строк длины $$$2$$$.