Lexicographically Smallest Binary String

You are given a binary string consisting of characters '0' and '1'. Your task is to convert the given string into the lexicographically smallest possible binary string that has the same count of '0's and '1's as the original string.

In other words, if the input binary string contains ( c_0 ) zeros and ( c_1 ) ones, then the output should be a string where all the zeros come first followed by all the ones, i.e., the output should be ( \underbrace{0 \ldots 0}{c_0} \underbrace{1 \ldots 1}{c_1} ).

The input begins with an integer ( T ) representing the number of test cases. Each of the following ( T ) lines contains a binary string. For each test case, print the lexicographically smallest possible binary string on a new line.

inputFormat

The first line of input contains a single integer ( T ) (( T \geq 1 )) which denotes the number of test cases. Each of the next ( T ) lines contains a binary string.

outputFormat

For each test case, output the lexicographically smallest binary string with the same number of zeros and ones as the given string. Each result should be printed on a new line.## sample

3
1100
10101
111000

0011
00111
000111