Вам дана бинарная строка \(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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач