#include"stdio.h"
#include"string.h"
void main()
{
  int n,i,j,k,l,c,w;
  char a[10000];
  float b[10000],t;
  scanf("%d",&n);
  while(n--)
  {
    c=1;
    scanf("%s",a);
    l=strlen(a);
    for(i=0;i<l;i++)
    {
      if(a[i]>='a'&&a[i]<='z')
      b[i]=a[i];
      if(a[i]<='Z'&&a[i]>='A')
      b[i]=(int)a[i]+31.5;
    }
    for(i=0;i<l;i++)
    {
      for(j=i+1;j<l;j++)
      {
        if(b[i]>b[j])
        {
         t=b[i];
         b[i]=b[j];
         b[j]=t;
        }
      }
    }
     for(i=0;i<l;i++)
     {
       w=(int)b[i];
       if((float)w==b[i])
       a[i]=b[i];
       else
       a[i]=(char)(b[i]-31.5);
     }
    printf("%s\n",a);
   while(1)
   {
    for(i=l-(1+c);i>=0;i--)
    {
      if(b[l-c]>b[i])
      {
        t=b[l-c];
        b[l-c]=b[i];
        b[i]=t;
        break;
      }
    }
    if(1+c==l+2)
    break;
    if(i<0)
    {c++;continue;}
    c=1;
    for(j=i+1;j<l;j++)
     {
       for(k=j+1;a[k]!='\0';k++)
       {
         if(b[k]<b[j])
          {
            t=b[k];
            b[k]=b[j];
            b[j]=t;
          }
       }
     }
     for(i=0;i<l;i++)
     {
       w=(int)b[i];
       if((float)w==b[i])
       a[i]=b[i];
       else
       a[i]=(char)(b[i]-31.5);
     }
     printf("%s\n",a);
   }
  }
}