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

В $$$2022$$$ году Миша нашёл два числа $$$a$$$ и $$$b$$$ длины $$$n$$$, записанных в двоичной системе счисления (то есть для их записи были использованы только цифры $$$0$$$ и $$$1$$$), оба из которых могут содержать ведущие нули. Чтобы их не забыть, он решил создать число $$$d$$$ следующим образом:

  • сначала он получит число $$$c$$$ в результате поразрядного сложения чисел $$$a$$$ и $$$b$$$ без переносов, из-за чего $$$c$$$ может содержать одну или более цифр $$$2$$$. Например, в результате поразрядного сложения чисел $$$0110$$$ и $$$1101$$$ получится число $$$1211$$$, a в результате поразрядного сложения чисел $$$011000$$$ и $$$011000$$$ получится $$$022000$$$.
  • после этого (чтобы запоминать меньше цифр) Миша заменит последовательные вхождения одной и той же цифры в $$$c$$$ на одну цифру, тем самым получив число $$$d$$$. В вышеописанном примере число $$$1211$$$ Миша заменит на $$$121$$$, а число $$$022000$$$ — на $$$020$$$ (таким образом, в числе $$$d$$$ не может быть двух одинаковых цифр подряд).
К сожалению, Миша потерял число $$$a$$$ до того, как вычислил $$$d$$$. Чтобы обрадовать его, Вы решили найти любое число $$$a$$$ длины $$$n$$$ такое, что $$$d$$$ будет максимально возможным как число.

Максимально возможным как число означает, что $$$102 > 21$$$, $$$012 < 101$$$, $$$021 = 21$$$ и тому подобное.

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

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

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длина чисел $$$a$$$ и $$$b$$$.

В следующей строке дано число $$$b$$$ длины $$$n$$$. Число $$$b$$$ состоит только из цифр $$$0$$$ и $$$1$$$.

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

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

Для каждого набора входных данных, выведите одно двоичное число $$$a$$$ длины $$$n$$$. Обратите внимание, что числа $$$a$$$ и $$$b$$$ могут содержать ведущие нули, но их длина должна быть равна $$$n$$$.

Пример
Входные данные
5
1
0
3
011
3
110
6
111000
6
001011
Выходные данные
1
110
100
101101
101110
Примечание

В первом наборе входных данных, $$$b = 0$$$ и при выборе $$$a = 1$$$ получится $$$d = 1$$$.

Во втором наборе, $$$b = 011$$$.

  • Если выбрать $$$a = 000$$$, $$$c$$$ будет равно $$$011$$$, и $$$d = 01$$$.
  • Если выбрать $$$a = 111$$$, $$$c$$$ будет равно $$$122$$$, и $$$d = 12$$$.
  • Если выбрать $$$a = 010$$$, получится $$$d = 021$$$.
  • Если выбрать $$$a = 110$$$, получится $$$d = 121$$$.
Можно показать, что ответ $$$a = 110$$$ является верным, и $$$d = 121$$$ является максимальным.

В третьем наборе, $$$b = 110$$$. При выборе $$$a = 100$$$ получится $$$d = 210$$$. Это максимальное возможное $$$d$$$ в данном случае.

В четвертом наборе, $$$b = 111000$$$. При выборе $$$a = 101101$$$ получится $$$d = 212101$$$. Это максимальное возможное $$$d$$$ в данном случае.

В пятом наборе, $$$b = 001011$$$. При выборе $$$a = 101110$$$ получится $$$d = 102121$$$. Это максимальное возможное $$$d$$$ в данном случае.