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

int comp(const void *c, const void *d)
{
	int valuea, valueb, sta, stb, a, b;
	a=*(char *)c;
	b=*(char *)d;
	if (a >= 'A' && a <= 'Z')
	{
		valuea = a - 'A';
		sta = 0;	
	}
	else
	{
		valuea = a - 'a';
		sta = 1;	
	}
		
	if (b >= 'A' && b <= 'Z')
	{
		valueb = b - 'A';
		stb = 0;	
	}
	else
	{
		valueb = b - 'a';
		stb = 1;	
	}
	
	if(valuea != valueb) 
	{
		return valuea - valueb;	
	}
	else
	{
		return sta - stb;	
	}
}

int main()
{
	char s[14],temp;
	int n,i,j,l;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",s);
		l=strlen(s);
		
		qsort(s, l, 1, comp);
				
		while(1)
		{
			printf("%s\n",s);
			for(i=l-2;i>=0;i--)
			{
				if(comp(&s[i], &s[i+1]) < 0) break;	
			}
			if(i==-1) break;
			for(j=l-1;j>i;j--)
			{
				if(comp(&s[j], &s[i]) > 0) break;	
			}
			temp=s[i];
			s[i]=s[j];
			s[j]=temp;
			i++;
			for(j=l-1;i<j;i++,j--){temp=s[i];s[i]=s[j],s[j]=temp;}
		}	
	}
	return 0;
}