Ли убирался у себя в дома перед вечеринкой, когда нашел под ковром «грязную» строку. Теперь он хочет очистить строку, но сделать это стильно...
Строка \(s\), которую нашел Ли, является двоичной строкой длины \(n\) (т. е. строка состоит только из символов 0 и 1).
За один шаг, он может выбрать два последовательных символа \(s_i\) и \(s_{i+1}\) и, если символ \(s_i\) равен 1 и \(s_{i + 1}\) равен 0, он может удалить ровно один из символов (Ли может выбрать какой удалить, но не может удалить оба символа одновременно). После удаления строка сжимается.
Ли может сделать произвольное количество шагов (возможно, ни одного шага) и он хочет сделать строку \(s\) как можно более чистой. Он считает, что из двух различных строк \(x\) и \(y\) более короткая строка чище, а если они равны по длине, то чище та, что лексикографически меньше.
Сейчас же вам необходимо ответить на \(t\) наборов входных данных: для \(i\)-го набора, выведите самую чистую строку, которую может получить Ли за произвольное количество шагов.
Небольшое напоминание: если у нас есть две строки \(x\) и \(y\) равной длины, то \(x\) лексикографически меньше чем \(y\), если существует такая позиция \(i\), что \(x_1 = y_1\), \(x_2 = y_2\),..., \(x_{i - 1} = y_{i - 1}\) и \(x_i < y_i\).
Выходные данные
Выведите \(t\) ответов — по одному на набор входных данных.
Ответом на \(i\)-й набор является самая чистая строка, которую может получить Ли за произвольное (возможно, нулевое) количество шагов.
Примечание
В первом наборе входных данных, Ли не может сделать ни одного шага.
Во втором наборе, Ли должен удалить \(s_2\).
В третьем наборе, Ли может, например, выполнить следующие шаги: 11001101 \(\rightarrow\) 1100101 \(\rightarrow\) 110101 \(\rightarrow\) 10101 \(\rightarrow\) 1101 \(\rightarrow\) 101 \(\rightarrow\) 01.