#include <iostream>

#include <algorithm>

using namespace std;

const int MAX_N = ;

char P[MAX_N], A[MAX_N];

char * SortAlp(char P[], int n)

{

    int Low[MAX_N], Upper[MAX_N];

    int LowLen, UpperLen;

    LowLen = UpperLen = ;

    for (int i = ; i < n; ++ i)

    {

        if ('A' <= P[i] && P[i] <= 'Z')

            Upper[UpperLen++] = P[i];

        else

            Low[LowLen++] = P[i];

    }

    sort(Low, Low + LowLen);

    sort(Upper, Upper + UpperLen);

    int Index_L, Index_U;

    Index_L = Index_U = ;

    for (int j = ; j < n; ++j)

    {

        if (Upper[Index_U] - 'A' + 'a' <= Low[Index_L]

            && Index_U < UpperLen)

            P[j] = Upper[Index_U++];

        else

            P[j] = Low[Index_L++];

    }

    return P;

}

void PrintPermutation(int n, char P[], char A[], int cur)

{

    int i, j;

    if (cur == n)

    {

        for (i = ; i < n; ++i)

            printf("%c", A[i]);

        printf("\n");

    }

    else

    {

        for (i = ; i < n; ++i)

        {

            if (!i || P[i] != P[i-])

            {

                int c1 = , c2 = ;

                for (j = ; j < cur; ++j)

                    if (A[j] == P[i]) c1++;

                for (j = ; j < n; ++j)

                    if (P[i] == P[j]) c2++;

                if (c1 < c2)

                {

                    A[cur] = P[i];

                    PrintPermutation(n, P, A, cur + );

                }

            }

        }

    }

}

int main()

{

    int n;

    char P[MAX_N];

    cin >> n;

    for (int i = ; i < n; ++i)

    {

        cin >> P;

        SortAlp(P, strlen(P));

        PrintPermutation(strlen(P), P, A, );

    }

    return ;

}