Largest Binary Number After One Operation

You are given a binary string s (composed of characters '0' and '1'). You are allowed to perform exactly one operation on this string, where the operation is one of the following:

• Flip exactly one bit in the string, i.e. change a '0' to a '1' or a '1' to a '0'.
• Swap exactly two different bits in the string.

Your task is to compute the lexicographically largest binary string possible after performing exactly one such operation.

For example, given s = "101", one of the optimal operations is to swap bits to form "111".

Note: The lexicographical order is the standard dictionary order where, for binary strings of the same length, "1" is considered greater than "0". In mathematical notation, if we denote the string as a sequence of characters \(s_1 s_2 \dots s_n\), then the maximum string is the one which is maximum in the order relation.

Formally, if you consider all strings \(t\) that can be obtained from \(s\) by performing exactly one allowed operation, you need to find:

\[ \max\{ t : t \text{ can be obtained from } s \text{ by one operation} \}. \]

inputFormat

The input is read from standard input (stdin) and has the following format:

T
s_1
s_2
... 
s_T

Where:

• T is an integer representing the number of test cases.
• Each s_i is a binary string.

outputFormat

For each test case, output the lexicographically largest binary string possible after performing exactly one allowed operation. Each result should be printed on its own line to standard output (stdout).

## sample

3
101
0110
101010

111
1110
111010

</p>