该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

盗将行，何以停，枕风宿雪独自迎

红昭愿，情人念，隔却山海几时恋

落花情，心难平，一种相思花飘零

对黄昏，泪滚滚，骗过天下笑昆仑

多情岸，怎相盼，饮马长川痴情叹

拜无忧，无处愁，千秋荒唐殿上留

梦回还，涂山栾，相思树下共婵娟

寄明月，人不绝，来去飘洒痴心掠

牵丝戏，人狐逆，扬汤止沸心难闭

典狱司，将军泣，故人终戏谁如意

东风志，忘羡誓，云深不知双骑驰

恨枉生，独守城，踽踽独行心已疯

将厌离，江厌离，道久忘归当厌离

何以歌，陈情和，一痴狂者笛吹彻

琵琶行，虾蟆陵，嘈嘈切切琴声宁

题目描述

给出一个长度为 $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$ 。

输入输出样例 #1

输入 #1

5
6
101011
5
00000
9
100100011
3
100
1
1

输出 #1

0010100
111111
0011111100
0110
11

说明/提示

考虑第一个例子：

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

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

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