Subsequence‐Inclusion and Substring‐Avoidance in Binary Strings

Given a binary string \(A\) of length \(n\) (with \(n\geq 2\)), you are to construct a binary string \(B\) of some length \(m\) which satisfies the following:

• \(B\) is a 0-1 string of length \(m\) (\(m\geq n+1\)).
• No contiguous substring of \(B\) is equal to \(A\). In other words, for every valid index \(i\) with \(1 \le i \le m-n+1\), \(B(i,i+n-1)\neq A\). (Here the substring \(B(i,i+n-1)\) denotes the \(n\) consecutive characters starting from position \(i\).)
• There exists at least one subsequence of \(B\) equal to \(A\). (A subsequence is obtained by deleting zero or more characters without changing the order.)

Important: The definition of substring is the usual one – a contiguous block of characters. The definition of subsequence is any sequence of characters obtained by choosing a strictly increasing sequence of indices. It can be proven that under the constraints given below, a solution always exists. In particular, note that if \(A\) is non-homogeneous (contains both 0 and 1) then we assume \(n\ge 3\); otherwise (if \(A\) is homogeneous) \(n\ge 2\>.

Task: You are given \(T\) queries. For each query, you are given a binary string \(A\) (which satisfies the above restrictions). For each query, output any binary string \(B\) meeting the requirements.

Example Explanation:
For homogeneous \(A\) (e.g. \(A=000\)), one valid construction is to let \[ B = A[1..n-1] \; || \; \overline{A[1]} \; || \; A[1], \] which yields \(B=0010\) for \(A=000\). For a non-homogeneous \(A\) with \(n\ge3\) (e.g. \(A=101\)), one valid construction is \[ B = A[1..n-1] \; || \; \overline{A[n]} \; || \; A[n], \] which yields \(B=1001\) for \(A=101\). Here, \(\overline{c}\) denotes the bit complement of bit \(c\) (i.e. \(\overline{0}=1\) and \(\overline{1}=0\)), and \(||\) denotes concatenation.

inputFormat

The input begins with an integer \(T\) (the number of queries). Each of the next \(T\) lines contains a binary string \(A\). It is guaranteed that for each query either \(A\) is homogeneous (all characters the same and \(n\ge2\)), or \(A\) is non-homogeneous with \(n\ge3\).

Example:
3
000
101
011

outputFormat

For each query, output a binary string \(B\) which satisfies the conditions. If there are multiple valid answers, output any one of them. (Each answer should be printed on a separate line.)

sample

3
000
101
011

0010
1001
0101