import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Set;
import java.io.IOException;
import java.util.HashMap;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.BufferedReader;
import java.util.Comparator;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author
 */
public class Main
{
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task195 solver = new Task195();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task195
	{
		Map<Character, Integer> orderMap = new HashMap<>();

		public void solve(int testNumber, InputReader in, PrintWriter out) {
			generateOrder();
			int n = in.nextInt();
			for (int i = 0; i < n; i++) {
				char[] word = in.nextLine().toCharArray();
				List<Character> wordList = convertToLexiList(word);
				Set<String> perms = permutations(wordList);
				for (String s : perms) {
					out.println(s);
				}
			}
		}

		private List<Character> convertToLexiList(char[] word) {
			List<Character> list = new ArrayList<>();
			for (int i = 0; i < word.length; i++) {
				list.add(new Character(word[i]));
			}
			Collections.sort(list, new LexiComparator());
			return list;
		}

		private void generateOrder() {
			orderMap.put('A', 0);
			orderMap.put('a', 1);
			orderMap.put('B', 2);
			orderMap.put('b', 3);
			orderMap.put('C', 4);
			orderMap.put('c', 5);
			orderMap.put('D', 6);
			orderMap.put('d', 7);
			orderMap.put('E', 8);
			orderMap.put('e', 9);
			orderMap.put('F', 10);
			orderMap.put('f', 11);
			orderMap.put('G', 12);
			orderMap.put('g', 13);
			orderMap.put('H', 14);
			orderMap.put('h', 15);
			orderMap.put('I', 16);
			orderMap.put('i', 17);
			orderMap.put('J', 18);
			orderMap.put('j', 19);
			orderMap.put('K', 20);
			orderMap.put('k', 21);
			orderMap.put('L', 22);
			orderMap.put('l', 23);
			orderMap.put('M', 24);
			orderMap.put('m', 25);
			orderMap.put('N', 26);
			orderMap.put('n', 27);
			orderMap.put('O', 28);
			orderMap.put('o', 29);
			orderMap.put('P', 30);
			orderMap.put('p', 31);
			orderMap.put('Q', 32);
			orderMap.put('q', 33);
			orderMap.put('R', 34);
			orderMap.put('r', 35);
			orderMap.put('S', 36);
			orderMap.put('s', 37);
			orderMap.put('T', 38);
			orderMap.put('t', 39);
			orderMap.put('U', 40);
			orderMap.put('u', 41);
			orderMap.put('V', 42);
			orderMap.put('v', 43);
			orderMap.put('W', 44);
			orderMap.put('w', 45);
			orderMap.put('X', 46);
			orderMap.put('x', 47);
			orderMap.put('Y', 48);
			orderMap.put('y', 49);
			orderMap.put('Z', 50);
			orderMap.put('z', 51);
		}

		Set<String> permutations(List<Character> word) {
			Set<String> perm = new TreeSet<>(new LexiStringComparator());
			if (word.size() == 1) {
				perm.add(String.valueOf(word.get(0)));
				return perm;
			}

			for (int i = 0; i < word.size(); i++) {
				String rem = Character.toString(word.get(i));
				List<Character> altered_word = new ArrayList(word);
				altered_word.remove(i);
				Set<String> k_perm = permutations(altered_word);
				for (String s : k_perm) {
					s = rem.concat(s);
					perm.add(s);
				}
			}
			return perm;
		}

		class LexiComparator implements Comparator<Character>
		{

			public int compare(Character first, Character second) {
				return orderMap.get(first).compareTo(orderMap.get(second));
			}

		}

		class LexiStringComparator implements Comparator<String>
		{

			public int compare(String first, String second) {
				LexiComparator cmp = new LexiComparator();
				int result = 0;
				for (int i = 0; i < first.length(); i++) {
					result = cmp.compare(first.charAt(i), second.charAt(i));
					if (result != 0) {
						return result;
					}
				}
				return 0;
			}

		}

	}

	static class InputReader
	{
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		public String next() {
			try {
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					tokenizer = new StringTokenizer(nextLine());
				}
				return tokenizer.nextToken();
			} catch (NullPointerException e) {
				return null;
			}
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}