Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

A. Ты удаляешь, я удаляю
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алисе и Бобу дана бинарная строка$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$. Она содержит как минимум один $$$\mathtt{0}$$$ и как минимум одну $$$\mathtt{1}$$$.

Они по очереди выполняют ровно одно действие в следующем порядке:

  • Сначала Алиса выбирает вхождение $$$\mathtt{0}$$$ в $$$s$$$ и удаляет его.
  • Затем Боб выбирает вхождение $$$\mathtt{1}$$$ в получившейся строке и удаляет его.

Алиса хочет, чтобы итоговая строка была лексикографически$$$^{\text{†}}$$$ как можно больше, а Боб хочет, чтобы она была лексикографически как можно меньше. Определите итоговую строку, если оба игрока действуют оптимально.

$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая только из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.

$$$^{\text{†}}$$$Для двух различных бинарных строк $$$a$$$ и $$$b$$$ одинаковой длины строка $$$a$$$ лексикографически меньше строки $$$b$$$, если в первой позиции, где они различаются, у $$$a$$$ стоит меньший символ.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке каждого набора входных данных дана бинарная строка $$$s$$$ длины $$$n$$$ ($$$3 \le n \le 100$$$).

Гарантируется, что $$$s$$$ содержит как минимум один $$$\mathtt{0}$$$ и как минимум одну $$$\mathtt{1}$$$.

Выходные данные

Для каждого набора входных данных выведите итоговую строку, если оба игрока действуют оптимально.

Пример
Входные данные
4
101
11001
0010
0101010000010100100101
Выходные данные
1
101
00
01010000010100100101
Примечание

В первом наборе входных данных Алиса обязана удалить единственный $$$\mathtt{0}$$$. Боб может удалить любое из двух вхождений $$$\mathtt{1}$$$, поэтому получается строка $$$\mathtt{1}$$$.

Во втором наборе входных данных Алиса может удалить любое из двух вхождений $$$\mathtt{0}$$$. Боб оптимально удаляет одно из первых двух вхождений $$$\mathtt{1}$$$, поэтому получается строка $$$\mathtt{101}$$$.

В третьем наборе входных данных Алиса может удалить любое вхождение $$$\mathtt{0}$$$. Затем Боб удаляет единственное вхождение $$$\mathtt{1}$$$, поэтому получается строка $$$\mathtt{00}$$$.