permutations

/*
    Given a string, print all permutations of a given string.

Input:
The first line of input contains an integer T, denoting the number of test cases.
Each test case contains a single string S in capital letter.

Output:
For each test case, print all permutations of a given string S with single space and all permutations should be in lexicographically increasing order.

Constraints:
1 ≤ T ≤ 10
1 ≤ size of string ≤ 5

Example:
Input:
2
ABC
ABSG
Output:
ABC ACB BAC BCA CAB CBA 
ABGS ABSG AGBS AGSB ASBG ASGB BAGS BASG BGAS BGSA BSAG BSGA GABS GASB GBAS GBSA GSAB GSBA SABG SAGB SBAG SBGA SGAB SGBA 
*/

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
	public static void main (String[] args)
	 {
	    Scanner sc=new Scanner(System.in);
	    int t=sc.nextInt();
	    while(t>0)
	    {
	        t--;
	        String s=sc.next();
	        char ch[]=new char[s.length()];
	        for(int i=0;i<ch.length;i++)
	            ch[i]=s.charAt(i);
	        Arrays.sort(ch);
	        s="";
	        for(int i=0;i<ch.length;i++)
	            s+=ch[i];
	        permutation("",s);
	        System.out.println();
	    }
	 }
	 
	 public static void permutation(String prev,String s)
	 {
	   int n=s.length();
	   if(n==0)
	        System.out.print(prev+" ");
	   else
	   {
	       for(int i=0;i<n;i++)
	            permutation(prev+s.charAt(i),s.substring(0,i)+s.substring(i+1));
	   }
	   
	 }
}