题目描述

给定长度为 $n$ 的 01 字符串 $S$，你可以进行任意多次（可能 $0$ 次）选择一个 $1<i<n$，并令 $S_i$ 变为 $S_{i-1}\operatorname{xor}S_{i+1}$。

请最大化最终 $S$ 中 $1$ 的数量，在此基础上，最小化 $S$ 的字典序。

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行一个整数 $n$ 表示 $S$ 的长度。

第二行一个 01 串 $S$。

输出格式

对于每组数据，输出一行一个 01 串表示答案。

2
5
01101
5
01010

01101
01110

样例解释 1

对于第二组数据，可以依次操作：01010 --> 01000 --> 01100 --> 01110。

数据范围

对于 $30\%$ 的数据，$T\leq 10$，$n\leq 10$，$S_1\neq S_n$。

对于 $60\%$ 的数据，$T\leq 10$，$n\leq 10^5$，$S_1\neq S_n$。

对于 $100\%$ 的数据，$1\leq T\leq 10^5$，$1\leq n\leq 10^5$，$1\leq \sum n\leq 10^6$，$S$ 中只包含 $0$ 和 $1$。