CF1867B.XOR Palindromes

You are given a binary string $s$ of length $n$ (a string that consists only of $0$ and $1$). A number $x$ is good if there exists a binary string $l$ of length $n$, containing $x$ ones, such that if each symbol $s_i$ is replaced by $s_i \oplus l_i$ (where $\oplus$ denotes the bitwise XOR operation), then the string $s$ becomes a palindrome.

You need to output a binary string $t$ of length $n+1$, where $t_i$ ($0 \leq i \leq n$) is equal to $1$ if number $i$ is good, and $0$ otherwise.

A palindrome is a string that reads the same from left to right as from right to left. For example, 01010, 1111, 0110 are palindromes.

给你一个长度为 $n$ 的二进制字符串 $s$（即仅由 $0$ 和 $1$ 组成的字符串）。一个数 $x$ 被称为“好的”，当且仅当存在一个长度为 $n$ 的二进制字符串 $l$，其中恰好包含 $x$ 个 $1$，使得将 $s$ 的每个字符 $s_i$ 替换为 $s_i \oplus l_i$（其中 $\oplus$ 表示按位异或运算）后，所得字符串 $s$ 成为一个回文串。

你需要输出一个长度为 $n+1$ 的二进制字符串 $t$，其中 $t_i$（$0 \leq i \leq n$）等于 $1$ 当且仅当数字 $i$ 是“好的”，否则为 $0$。

回文串是指从左到右读与从右到左读完全相同的字符串。例如，01010、1111、0110 都是回文串。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains a binary string $s$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output a single line containing a binary string $t$ of length $n+1$ - the answer to the problem.

对于每个测试用例，输出一行长度为 $n+1$ 的二进制字符串 $t$ —— 即该问题的答案。

Consider the first example.

• $t_2 = 1$ because we can choose $l = $ 010100, then the string $s$ becomes 111111, which is a palindrome.
• $t_4 = 1$ because we can choose $l = $ 101011.
• It can be shown that for all other $i$, there is no answer, so the remaining symbols are $0$.

考虑第一个例子。

• $t_2 = 1$，因为我们可选择 $l = $ 010100，此时字符串 $s$ 变为 111111，这是一个回文串。
• $t_4 = 1$，因为我们可选择 $l = $ 101011。
• 可以证明：对所有其他 $i$，均无解，因此其余符号均为 $0$。