長さ $n$ の 0 と 1 のみからなる文字列 $s$ が与えられます。あなたは以下の操作を任意の回数（0回でもよい）行うことができます。

• 先頭と末尾の文字が異なる部分文字列を選択し、その部分文字列を削除する。

例えば、$s = 0001110$ の場合、部分文字列 $001$ は先頭と末尾の文字が異なります。この部分文字列を選択して削除すると、元の文字列は $0110$ になります。

任意の回数操作を行った後の、文字列 $s$ の辞書順最小のものは何でしょうか。

† 2 つの文字列 $s$ と $t$ について、最初に異なる文字が現れる位置を $i$ とします。$s_i$ が $0$ で $t_i$ が $1$ である場合、$s$ は $t$ より辞書順で小さいと言います。そのような $i$ が存在しない場合、長さが短い方の文字列が辞書順で小さいと言います。空文字列は他のどの文字列よりも辞書順で小さいものとします。

入力形式

各テストファイルには複数のテストケースが含まれます。最初の行にテストケースの数 $T$ ($1 \le T \le 10^5$) が与えられます。各テストケースの形式は以下の通りです。

最初の行に文字列の長さを表す整数 $n$ ($1 \le n \le 10^6$) が与えられます。 次の行に $0$ と $1$ のみからなる長さ $n$ の文字列 $s$ が与えられます。

各テストファイルにおいて、すべてのテストケースの $n$ の総和は $10^6$ を超えないことが保証されます。

出力形式

各テストケースについて、操作によって得られる辞書順最小の文字列を1行で出力してください。特に、答えが空文字列である場合は "empty" と出力してください。

入出力例

入力 1

4
2
01
4
0010
5
10011
5
11011

出力 1

empty
0
empty
11