#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Function to compare strings lexicographically for sorting
int compare(const void *a, const void *b) {
    return strcmp((char *)a, (char *)b);
}

// Function to generate the next lexicographical permutation
int next_permutation(char *str) {
    int i = strlen(str) - 1;

    // Step 1: Find the rightmost character which is smaller than the next character
    while (i > 0 && str[i - 1] >= str[i]) {
        i--;
    }

    // Step 2: If there is no such character, we've generated all permutations
    if (i == 0) {
        return 0;
    }

    // Step 3: Find the character to swap with (next larger character to the right)
    int j = strlen(str) - 1;
    while (str[j] <= str[i - 1]) {
        j--;
    }

    // Step 4: Swap the characters
    char temp = str[i - 1];
    str[i - 1] = str[j];
    str[j] = temp;

    // Step 5: Reverse the suffix
    j = strlen(str) - 1;
    while (i < j) {
        temp = str[i];
        str[i] = str[j];
        str[j] = temp;
        i++;
        j--;
    }

    return 1;
}

void generatePermutations(char *str) {
    // Sort the string to get the first permutation in lexicographical order
    qsort(str, strlen(str), sizeof(char), compare);

    // Print the first permutation
    printf("%s ", str);

    // Generate and print the next permutations until no more are possible
    while (next_permutation(str)) {
        printf("%s ", str);
    }

    printf("\n");
}

int main() {
    int T;
    scanf("%d", &T);  // Read number of test cases

    while (T--) {
        char str[6];  // Only up to 5 characters are allowed
        scanf("%s", str);  // Read the string
        generatePermutations(str);  // Generate and print permutations
    }

    return 0;
}