#include<stdio.h>
char Bubblesort(char *,int);
char SelectionSort(char*,int);
int main(){
int n,i;
scanf("%d",&n);
if(n<1||n>36)return 0;
char *s[n];
for(i=0;i<n;i++){
  scanf("%s",s[i]);
}
for(i=0;i<n;i++){
printf("%s\n",Bubblesort(*s,n));
printf("%s\n",SelectionSort(*s,n));
s++;
}
return 0;
}

char Bubblesort(char *s,int n){
int i,j;
char a;
for(i=0;i<n;i++){
  for(j=n-1;j<i+1;j--){
      if(s[j]<s[j-1]){
  a=s[j];
  s[j]=s[j-1];
  s[j-1]=a;
    }
  }
}
return *s;
}

char SelectionSort(char *s,int n){
  int i,j;
  int min;
  char a;
  for(i=0;i<n;i++){
    min=i;
    for(j=i;j<n;j++){
      if(s[j]<s[min]){
        min=j;
      }
a=s[i];
s[i]=s[min];
s[min]=a;
    }
  }
return *s;
}

