CF1342B Binary Period

Let's say string $ s $ has period $ k $ if $ s_i = s_{i + k} $ for all $ i $ from $ 1 $ to $ |s| - k $ ( $ |s| $ means length of string $ s $ ) and $ k $ is the minimum positive integer with this property. Some examples of a period: for $ s $ ="0101" the period is $ k=2 $ , for $ s $ ="0000" the period is $ k=1 $ , for $ s $ ="010" the period is $ k=2 $ , for $ s $ ="0011" the period is $ k=4 $ . You are given string $ t $ consisting only of 0's and 1's and you need to find such string $ s $ that: 1. String $ s $ consists only of 0's and 1's; 2. The length of $ s $ doesn't exceed $ 2 \cdot |t| $ ; 3. String $ t $ is a subsequence of string $ s $ ; 4. String $ s $ has smallest possible period among all strings that meet conditions 1—3. Let us recall that $ t $ is a subsequence of $ s $ if $ t $ can be derived from $ s $ by deleting zero or more elements (any) without changing the order of the remaining elements. For example, $ t $ ="011" is a subsequence of $ s $ ="10101".

The first line contains single integer $ T $ ( $ 1 \le T \le 100 $ ) — the number of test cases. Next $ T $ lines contain test cases — one per line. Each line contains string $ t $ ( $ 1 \le |t| \le 100 $ ) consisting only of 0's and 1's.

Print one string for each test case — string $ s $ you needed to find. If there are multiple solutions print any one of them.

In the first and second test cases, $ s = t $ since it's already one of the optimal solutions. Answers have periods equal to $ 1 $ and $ 2 $ , respectively. In the third test case, there are shorter optimal solutions, but it's okay since we don't need to minimize the string $ s $ . String $ s $ has period equal to $ 1 $ .