B. Палиндромный XOR
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная строка $$$s$$$ длины $$$n$$$ (строка - состоящая только из $$$0$$$ и $$$1$$$). Число $$$x$$$ является хорошим, если существует такая бинарная строка $$$l$$$ длины $$$n$$$, содержащая $$$x$$$ единиц, что если каждый символ $$$s_i$$$ заменить на $$$s_i \oplus l_i$$$ (где $$$\oplus$$$ обозначает операцию Побитового исключающего ИЛИ) то строка $$$s$$$ станет палиндромом.

Нужно вывести бинарную строку $$$t$$$ длины $$$n+1$$$, где $$$t_i$$$ ($$$0 \leq i \leq n$$$) равно $$$1$$$ если число $$$i$$$ хорошее, и $$$0$$$ иначе.

Палиндром — это строка, которая читается одинаково как слева направо, так и справа налево. Например, строки 01010, 1111, 0110 — палиндромы.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$.

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

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

Для каждого набора входных данных выведите одну строку $$$t$$$ длины $$$n+1$$$ - ответ на задачу.

Пример
Входные данные
5
6
101011
5
00000
9
100100011
3
100
1
1
Выходные данные
0010100
111111
0011111100
0110
11
Примечание

Рассмотрим первый пример.

  • $$$t_2 = 1$$$ так как можно выбрать $$$l = $$$ 010100 тогда строка $$$s$$$ станет равна 111111, что является палиндромом.
  • $$$t_4 = 1$$$ так как можно выбрать $$$l = $$$ 101011.
  • Можно показать, что для всех остальных $$$i$$$ ответа не существует, поэтому остальные символы равны $$$0$$$.