题目描述

给出长度为01串 \(S\)，你可以执行以下操作若干次：

• 选择串 \(S\) 的一个子串 \(S[l:r]\)，满足其首字符和尾字符不同，即 \(S_l \ne S_r\)，将该子串从 \(S\) 中删除（变为 \(S[1:l-1]\,+\,S[r+1:|S|]\)）。

请问，经过零次或多次上述操作后，能够得到的字典序最小的串是什么？（字典序按“字符越小越前”比较，空串最小）

输入格式

T
S₁
S₂
⋮
S_T

• 第一行包含一个正整数 \(T\)——测试用例数。
• 接下来 \(T\) 行，每行给出一个由 0 和 1 组成的非空字符串 \(S_i\)。

输出格式

对每个测试用例，输出一行，包含删除操作后能得到的字典序最小的 01 串（可以为空串，直接输出空行）。

样例

样例输入

3
01
0
111

样例输出

0
111

• 对于 S = "01"：可以把整个串删光，得到空串（最小）。
• 对于 S = "0"：无法执行任何删法，只能保持 "0"。
• 对于 S = "111"：所有字符相同，无法删出首尾异字符的子串，只能保留原串。

数据范围与提示

• \(1 \le T \le 10^5\)
• \(\sum_{i=1}^T |S_i| \le 10^6\)
• 每个 \(S_i\) 仅由字符 '0' 和 '1' 组成，长度至少 1。
• 要求整体算法 \(O(\sum |S|)\) 或 \(O(\sum |S|\log|S|)\) 通过。