string s;
int N;
bool cmp(char c1, char c2) {
	if (c1 >= 'a'&&c1 <= 'z'&&c2 >= 'a'&&c2 <= 'z')return c1 < c2;
	if (c1 >= 'A'&&c1 <= 'Z'&&c2 >= 'A'&&c2 <= 'Z')return c1 < c2;
	if (c1 >= 'a'&&c1 <= 'z'&&c2 >= 'A'&&c2 <= 'Z') {
		return c1 - 'a' < c2 - 'A';
	}
	if (c2 >= 'a'&&c2 <= 'z'&&c1 >= 'A'&&c1 <= 'Z') {
		if (c2 - 'a' == c1 - 'A')return true;
		return c1 - 'A' < c2 - 'a';
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s;
		sort(s.begin(), s.end(), cmp);
		printf("%s\n", s.c_str());
		while (next_permutation(s.begin(), s.end(),cmp)) {
				printf("%s\n", s.c_str());
		}
	}
}