// 给你字符串 按字典序输出所有排列
// 要是每个字母都不同 可以直接dfs ^_^
// 用前面说的生成排列算法 也可以直接 stl next_permutation

#include <iostream>

#include <string>

#include<sstream>

#include <cmath>

#include <map>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

char s[];

int n;

void change(int l,int r)

{

     while(l<r)

     {

         swap(s[l],s[r]);

         l++;

         r--;

     }

}

 bool permutation()

 {

     int i=n-;

     while(i>&&s[i-]>=s[i]) i--;

     if(!i) return false;

     int k=i,j=n-;

     for(;j>i;j--)

      if(s[j]>s[i-]){

          k=j;

          break;

     }

     swap(s[i-],s[k]);

     change(i,n-);

     return true;

 }

int main()

{

   int T;

   scanf("%d",&T);

   while(T--)

   {

       scanf("%s",s);

       n=strlen(s);

       sort(s,s+n);

       do

       {

           printf("%s\n",s);

       }while(permutation());

       printf("\n");

   }

   return ;

}