Smallest Lexicographic Binary String

Given a binary string consisting solely of characters '0' and '1', your task is to produce the lexicographically smallest string by performing any number of allowed swap operations. In one operation, you can select two indices i and j (1 ≤ i, j ≤ n) provided that the characters at these positions are different (i.e. one is '0' and the other is '1') and swap them.

Since swaps are only allowed between differing characters, if the string contains both '0's and '1's, you can effectively rearrange the string arbitrarily. Thus, the lexicographically smallest string will have all the '0's first, followed by all the '1's. Formally, if a string of length (n) contains (k) zeros, the smallest string is given by (0^k1^{n-k}).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) (1 ≤ (T) ≤ 1000), representing the number of test cases. Each of the following (T) lines contains a binary string composed only of the characters '0' and '1'. Each string has a length between 1 and 1000.

outputFormat

For each test case, output the lexicographically smallest binary string obtainable through the allowed swap operations. Each result should be printed on a new line to standard output (stdout).## sample

1
101

011