UPSUB - Up Subsequence


If x = a0a1a2...an-1 is a string where ai denotes the character at index i, a subsequence aj0aj1aj2...ajn is called an upsubsequence if aj0 <= aj1 <= aj2 <= ... <= ajn and j0 < j1 < j2 < ... < jn.

A maximal upsubsequence of a string is defined as the upsubsequence of maximum length. BuggyD observes that a string x can have many maximal upsubsequences. Help him find all the maximal upsubsequences in x.

Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

Each test case consists of a single line containing a string x, where the length of x is no more than 100. x will not contain any spaces, tabs or other whitespace characters.

Output

For each test csae, output all of the maximal upsubsequences of x in lexicographical order. Print a blank line after each test case.

Example

Input:
1
abcbcbcd

Output:
abbbcd
abbccd
abcccd

hide comments
Shubham: 2016-05-18 17:46:30

solve TRIP first :D :D

Ankit: 2015-10-15 18:04:26

moving backwards will automatically give sorted order :)

Praneeth.N: 2015-02-26 02:36:14

I am not sure why the problem is giving wrong answer inspite of covering all the cases...Can some one kindly give some hints or a test case where there is chance of getting wrong answer..

Zen: 2014-08-19 10:54:55

:D

kipoujr: 2011-10-19 18:20:57

You forgot to place a '\n' character at the end of the file! Please correct.


Added by:Matthew Reeder
Date:2006-10-30
Time limit:0.309s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2006