UVa 195 - Anagram

// UVa 195 - Anagram

#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

bool comp(char a, char b) {
	int aa, bb;
	if (0 <= a - 'A' && a - 'A' <= 25)
		aa = (a - 'A') * 2;
	else
		aa = (a - 'a') * 2 + 1;
	if (0 <= b - 'A' && b - 'A' <= 25)
		bb = (b - 'A') * 2;
	else
		bb = (b - 'a') * 2 + 1;
	return aa < bb;
}

int main() {
	int n;
	cin >> n;
	for (; n > 0; n--) {
		string word;
		cin >> word;
		sort(word.begin(), word.end(), comp);
		do {
			cout << word << endl;
		} while (next_permutation(word.begin(), word.end(), comp));
	}
	return 0;
}