You are given a string 'STR' containing lowercase English letters from a to z inclusive. Your task is to find all non-empty possible subsequences of 'STR'.

A Subsequence of a string is the one which is generated by deleting 0 or more letters from the string and keeping the rest of the letters in the same order.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then T test cases follow.

The first and only line of each test case contains string 'STR'. 

Output Format

For each test case, print the subsequences of the string 'STR' separated by space.

The output of each test case is printed in a separate line.

The output strings can be returned in any order.

Note

You don’t have to print anything, it has already been taken care of. Just implement the function. 

Constraints:

1 <= T <= 10 
1 <=  |STR| <= 16

Where |STR| represents the length of the string 'STR'.

Time Limit: 1 sec