题目描述

给出一个长度为 $n$ 的 $01$ 串(只含 $0,1$ 的字符串) $s$。定义一个数 $x$ 是好数，当仅当存在一个长度也为 $n$ 的 $01$ 串 $l$ 使得对于所有的 $s_i$ 被 $s_i\oplus l_i$ 替换后得到的 $01$ 串是一个回文串。

对于给出的一组 $n,s$ ，你需要给出一个长度为 $n+1$ 的 $01$ 串 $t$ ，$t_i=1$ 当仅当 $i$ 是一个好数。注意，$t$ 从 $0$ 开始编号

题目中 $\oplus$ 表示异或。

回文串指正着读反着读都相同的字符串，比如 $0110,01010,1111$ 都是回文串。

输入格式

每个测试点有多组数据。对于每个测试点，第一行为一个整数 $t$，代表有 $t (1\leq t\leq 10^5)$ 组数据。

对于每组数据，第一行为一个整数 $n (1 \leq n\leq 10^5)$。

第二行是一行长度为 $n$ 的 $01$ 串 $s$。

保证单个测试点所有 $n$ 的和不超过 $10^5$

输出格式

对于每组数据，输出一行长度为 $n+1$ 的 $01$ 串 $l$ 。

说明/提示

考虑第一个例子：

$t_2=1$ 是因为我们可以选到 $l=010100$ ，异或后 $s$ 变成 $111111$ 成为一个回文串。

$t_4=1$ 是因为我们可以选到 $l=101011$ 此时 $s$ 变成回文串 $000000$。

可以证明其他任意的 $i$ 都不满足成为 “好数” 的条件，故其他所有的位置都是 $0$。

样例

5
6
101011
5
00000
9
100100011
3
100
1
1

0010100
111111
0011111100
0110
11