B'Polycarp has a string s . Polycarp performs the following actions until the string s is empty ( t is initially an empty string): Polycarp performs this sequence of actions strictly in this order. Note that after Polycarp finishes the actions, the string s will be empty and the string t will be equal to some value (that is undefined and depends on the order of removing). E.g. consider s ="abacaba" so the actions may be performed as follows: You need to restore the initial value of the string s using only the final value of t and find the order of removing letters from s . The first line contains one integer T ( 1 <= T <= 10^4 ) -- the number of test cases. Then T test cases follow. Each test case contains one string t consisting of lowercase letters of the Latin alphabet. The length of t doesn 't exceed 5 cdot 10^5 . The sum of lengths of all strings t in the test cases doesn 't exceed 5 cdot 10^5 . For each test case output in a separate line: The first test case is considered in the statement. '...