Дано двійковий рядок $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