Dany jest ciąg $s$ o długości $n$, składający się wyłącznie z znaków $0$ i $1$. Możesz wykonać dowolną liczbę operacji (w tym zero):

• Wybierz podciąg, którego pierwszy i ostatni znak są różne, a następnie usuń ten podciąg.

Na przykład, dla $s = 0001110$, podciąg $001$ ma różne znaki na początku i końcu. Po wybraniu i usunięciu tego podciągu, ciąg staje się $0110$.

Jaki jest najmniejszy możliwy porządek leksykograficzny $^\dagger$ ciągu $s$ po wykonaniu dowolnej liczby operacji?

$^\dagger$ Dla dwóch ciągów $s$ i $t$, niech $i$ będzie pierwszą pozycją, na której się różnią. Jeśli $s_i$ to $0$, a $t_i$ to $1$, mówimy, że $s$ jest leksykograficznie mniejszy od $t$. Jeśli takie $i$ nie istnieje, mniejszy jest ciąg krótszy. Pusty ciąg jest leksykograficznie mniejszy od każdego innego ciągu.

Wejście

Każdy plik testowy zawiera wiele zestawów danych. Pierwsza linia zawiera liczbę zestawów danych $T$ ($1 \le T \le 10^5$). Format każdego zestawu danych jest następujący:

Pierwsza linia zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$), oznaczającą długość ciągu. Druga linia zawiera ciąg $s$ o długości $n$, składający się wyłącznie z znaków $0$ i $1$.

W każdym pliku testowym suma $n$ dla wszystkich zestawów danych nie przekracza $10^6$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii ciąg znaków reprezentujący najmniejszy leksykograficznie ciąg, jaki można uzyskać poprzez operacje. W szczególności, jeśli odpowiedzią jest pusty ciąg, wypisz "empty".

Przykład

Wejście 1

4
2
01
4
0010
5
10011
5
11011

Wyjście 1

empty
0
empty
11