题目描述

Dave 有一个 01 串。

Dave 每次操作可以删除一个形如 01 或者 10 的子串，例如 111001 -> 1110 -> 11。他希望这个串的字典序尽可能的小，所以 Dave 想知道最优操作下，可以获得的字典序最小的字符串是什么。

注意：空串的字典序小于任意串的字典序。如果可以变成空串，请输出 EMPTY。

输入格式

第一行一个整数 $T$ 表示询问组数。

接下来 $T$ 组询问：

每组询问第一行一个整数 $n$，代表 01 串的长度。

接下来一行一个长为 $n$ 的 01 串。

输出格式

共 $T$ 行，每行一个 01 串，代表该组询问最优操作下可以获得的字典序最小的字符串。如果答案是空串，输出 EMPTY。

4
2
01
3
011
3
110
5
00001

EMPTY
011
1
000

数据范围

对于 $30\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 20$； 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 5 \cdot 10^5$，$1 \le \sum n \le 5 \cdot 10^5$。