Lexicographical Permutations

Given a number of test cases, each containing a single string, your task is to generate all possible permutations of each string in lexicographical order. Recall that for a string of length \(n\), there are \(n!\) possible permutations if all characters are distinct.

The output for each test case should be a single line where the permutations are separated by a single space.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\) representing the number of test cases. This is followed by \(T\) lines, each containing a single string.

Example:

2
abc
dog

outputFormat

For each test case, output a single line with all lexicographically ordered permutations of the given string. Each permutation should be separated by a single space.

Example output for the above input:

abc acb bac bca cab cba
dgo dog gdo god odg ogd

## sample

1
abc

abc acb bac bca cab cba

</p>