Дана двоичная строка $s$ длины $n$ (строка из символов $01$). Вам нужно заменить один символ в подстроке $s[2 \ldots n - 1]$ на $\oplus$ так, чтобы итоговое значение выражения было как можно большим.

$\oplus$ обозначает операцию двоичного исключающего ИЛИ (XOR). После замены обе части по разные стороны от $\oplus$ рассматриваются как двоичные числа.

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

Один тест содержит несколько наборов данных.

Первая строка входных данных содержит число наборов данных $T$ ($1 \le T \le 10^5$), обозначающее количество наборов данных в этом тесте.

Для каждого набора данных дана одна строка, содержащая двоичную строку $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Гарантируется, что в одном тесте $\sum |s| \le 5 \cdot 10^5$.

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

Для каждого набора данных выведите одну строку, содержащую двоичную строку, которая представляет наибольший результат в двоичном виде (строка числа не может содержать ведущих символов $0$, за исключением единственной цифры $0$).

Примеры

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

5
010
0110
1000
10101
01000

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

0
10
10
100
10