Magic Contest

本题是一道两阶段问题。

爱丽丝和鲍勃是著名的魔术师。他们决定与助手凯瑟琳一起在魔术比赛中表演如下魔术。

• 首先，鲍勃进入一个房间并与外界断开联系。鲍勃只能与凯瑟琳联系。凯瑟琳将一个长度为 $N$ 的二进制字符串 $S$ 告诉爱丽丝。
• 爱丽丝构造一个长度在 $N$ 到 $2N+100$ 之间的二进制字符串，并将其交给凯瑟琳。
• 凯瑟琳在收到的字符串的任意位置插入一个字符 0 或 1，再将所得字符串交给鲍勃。
• 鲍勃必须根据收到的字符串还原原字符串 $S$。

第一次运行的输入格式如下。

0 $T$ $N_1$ $S_1$

第一次运行时，对于每个测试用例，输出一行交给凯瑟琳的二进制字符串，共输出 $T$ 行。

设第 $i$ 个测试用例中输出字符串的长度为 $M_i$，则必须满足 $N_i\leq M_i\leq 2N_i+100$。

• $1\leq T\leq 1\,000$。
• $1\leq N_i\leq 200\,000$ ()。

鲍勃必须正确还原所有测试用例的原字符串 $S$。如果任意一个字符串未被正确还原，该提交得 $0$ 分。

如果所有字符串均被正确还原，得分由爱丽丝输出的字符串长度决定。对于第 $i$ 个测试用例，设原字符串长度为 $N_i$，爱丽丝输出的字符串长度为 $M_i$。定义