If x = a₀a₁a₂ ... a_n-1 is a string where a_i denotes the character at index i, a subsequence a_j0a_j1a_j2 ... a_jn is called an upsubsequence if a_j0 ≤ a_j1 ≤ a_j2 ≤ ... ≤ a_jn 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 case, 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