Distinct Permutations

Given a string, generate all distinct permutations of its characters in lexicographical order. You are given multiple test cases; for each test case, process the input string and output its distinct permutations, separated by a single space. This problem requires handling duplicate characters correctly.

The permutations for each string should be computed in lexicographical order. If the string contains duplicate characters, ensure that duplicate permutations are not printed.

Note: All input should be read from standard input and all output should be written to standard output.

inputFormat

The first line contains an integer T, representing the number of test cases. Each of the next T lines contains a non-empty string S.

outputFormat

For each test case, output a single line containing all distinct permutations of the string S in lexicographical order, separated by a single space.## sample

2
abc
aab

abc acb bac bca cab cba
aab aba baa