/* package whatever; // don't place package name! */
import java.util.*;
import java.io.*;
import java.lang.*;
class genfast
{
public static void main
(String[] args
) {
Scanner sc
= new Scanner
(System.
in); int t= sc.nextInt();
for (int i =0; i<t ; i++)
{
char [] a =sc.next().toCharArray();
do
{
bf.
append(new String(a
)+"\n"); }while(permutation(a));
}
}
public static boolean permutation(char a[])
{
for(int i = a.length-2,j; i >= 0; i--)
{
if (a[i+1] > a[i])
{
for( j = a.length-1; a[j] <= a[i]; j--);
swap(a, i, j);
for( j = 1; j <= (a.length-i)/2; j++)
swap(a, i+j, a.length-j);
return true;
}
}
return false;
}
public static void swap(char a[], int i, int j)
{
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5pby4qOwppbXBvcnQgamF2YS5sYW5nLio7CgpjbGFzcyBnZW5mYXN0CnsKCnB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpCnsKICAgIFNjYW5uZXIgc2MgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwogICAgaW50IHQ9IHNjLm5leHRJbnQoKTsKICAgIFN0cmluZ0J1ZmZlciBiZiA9IG5ldyBTdHJpbmdCdWZmZXIoIiIpOwogICAgZm9yIChpbnQgaSA9MDsgaTx0IDsgaSsrKQogICAgewogICAgICAgCiAgICAgICAgY2hhciBbXSBhID1zYy5uZXh0KCkudG9DaGFyQXJyYXkoKTsKICAgICAgICBBcnJheXMuc29ydChhKTsKICAgICAgICBkbwogICAgICAgIHsKICAgICAgICAgICAgYmYuYXBwZW5kKG5ldyBTdHJpbmcoYSkrIlxuIik7CiAgICAgICAgfXdoaWxlKHBlcm11dGF0aW9uKGEpKTsKICAgIH0KICAgIFN5c3RlbS5vdXQucHJpbnRsbihiZik7Cn0KIHB1YmxpYyBzdGF0aWMgYm9vbGVhbiBwZXJtdXRhdGlvbihjaGFyIGFbXSkKICAgIHsKICAgICAgIGZvcihpbnQgaSA9IGEubGVuZ3RoLTIsajsgaSA+PSAwOyBpLS0pCiAgICAgICB7CiAgICAgICAgaWYgKGFbaSsxXSA+IGFbaV0pCiAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvciggaiA9IGEubGVuZ3RoLTE7IGFbal0gPD0gYVtpXTsgai0tKTsKICAgICAgICAgICAgICAgIHN3YXAoYSwgaSwgaik7CiAgICAgICAgICAgICAgICBmb3IoIGogPSAxOyBqIDw9IChhLmxlbmd0aC1pKS8yOyBqKyspCiAgICAgICAgICAgICAgICBzd2FwKGEsIGkraiwgYS5sZW5ndGgtaik7CiAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgICAgfQogICAgICAgfQogICAgICAgcmV0dXJuIGZhbHNlOwogICB9CiAgIApwdWJsaWMgc3RhdGljIHZvaWQgc3dhcChjaGFyIGFbXSwgaW50IGksIGludCBqKQogewogIGNoYXIgdGVtcCA9IGFbaV07CiAgYVtpXSA9IGFbal07CiAgIGFbal0gPSB0ZW1wOwogICAgICB9Cn0=