Problem: Permutations of a String

Given a string STR consisting of lowercase English letters, your task is to return all permutations of the given string in lexicographically increasing order.

Explanation:

A string A is lexicographically less than string B if either A is a prefix of B (and A ≠ B), or there exists such 'i' (1 ≤ i ≤ min(|A|, |B|)), that A[i] < B[i], and for any 'j' (1 ≤ j < i), A[j] = B[j]. Here |A| denotes the length of the string A.

Input:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow.

The first and only line of each test case contains a string STR consisting of lowercase English letters.

Output:

For every test case, the permutations of the given string are printed in lexicographically increasing order separated by space.

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

Example:

Input:
1
bca

Output:
abc acb bac bca cab cba

Constraints:

• 1 ≤ T ≤ 5
• 1 ≤ |STR| ≤ 9 where |STR| is the length of the string.
• Time Limit: 1 sec

Note:

The given string contains unique characters.