Cho một xâu nhị phân $s$ có độ dài $n$ (xâu $01$). Bạn cần thay thế một ký tự trong $s[2 \ldots n - 1]$ bằng $\oplus$, sao cho giá trị cuối cùng của biểu thức là lớn nhất có thể.

$\oplus$ biểu thị phép toán XOR nhị phân. Sau khi thay thế, cả hai vế của $\oplus$ đều được coi là các số nhị phân.

Dữ liệu vào

Một test đơn lẻ chứa nhiều bộ dữ liệu.

Dòng đầu tiên của dữ liệu vào là số lượng bộ dữ liệu $T$ ($1 \le T \le 10^5$), biểu thị số bộ dữ liệu trong test này.

Với mỗi bộ dữ liệu, có một dòng chứa một xâu nhị phân $s$ ($3 \le |s| \le 5 \cdot 10^5$).

Đảm bảo rằng trong một test đơn lẻ, $\sum |s| \le 5 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một xâu nhị phân biểu thị kết quả lớn nhất dưới dạng nhị phân (xâu số không được chứa các chữ số $0$ ở đầu ngoại trừ trường hợp số $0$ có một chữ số duy nhất).

Ví dụ

Dữ liệu vào 1

5
010
0110
1000
10101
01000

Dữ liệu ra 1

0
10
10
100
10