Given a binary string $s$ of length $n$ ($01$ string). You need to replace one character in $s[2 \ldots n - 1]$ with $\oplus$, so that the final value of the expression is as large as possible.

$\oplus$ represents the binary XOR operation. After the replacement, both sides of $\oplus$ are treated as binary numbers.

Input

A single test case contains multiple data sets.

The first line of input is the number of data sets $T$ ($1 \le T \le 10^5$), representing the number of data sets in this test case.

For each data set, there is one line containing a binary string $s$ ($3 \le |s| \le 5 \cdot 10^5$).

It is guaranteed that in a single test case, $\sum |s| \le 5 \cdot 10^5$.

Output

For each data set, output one line containing a binary string that represents the largest result in binary form (the number string cannot contain leading $0$s except for the single digit $0$).

Examples

Input 1

5
010
0110
1000
10101
01000

Output 1

0
10
10
100
10