import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

immutable int letters = 26;

string solve (string s)
{
	int [letters] d;
	foreach (ref c; s)
	{
		d[c - 'a'] += 1;
	}

	foreach (let; 0..letters)
	{
		if (d[let] == 1)
		{
			string res;
			res ~= cast (char) (let + 'a');
			d[let] -= 1;
			foreach (x; 0..letters)
			{
				foreach (y; 0..d[x])
				{
					res ~= cast (char) (x + 'a');
				}
			}
			return res;
		}
	}

	foreach (let; 0..letters)
	{
		if (d[let] > 0)
		{
			string res;
			res ~= cast (char) (let + 'a');
			d[let] -= 1;
			string [2] add;
			foreach (x; 0..letters)
			{
				foreach (y; 0..d[x])
				{
					add[x > let] ~= cast (char) (x + 'a');
				}
			}

			if (add[0].length <= add[1].length + 1)
			{
				while (!add[0].empty || !add[1].empty)
				{
					foreach (v; 0..2)
					{
						if (!add[v].empty)
						{
							res ~= add[v][0];
							add[v].popFront ();
						}
					}
				}
				return res;
			}

			if (add[1].empty || add[1].front == add[1].back)
			{
				res ~= add[1];
				res ~= add[0];
				return res;
			}

			auto second = add[1][0];
			res ~= second;
			add[1].popFront ();
			res ~= add[0];
			foreach (i, ref c; add[1])
			{
				if (c != second)
				{
					res ~= c;
					res ~= add[1][0..i];
					res ~= add[1][i + 1..$];
					return res;
				}
			}

			assert (false);
		}
	}

	assert (false);
}

void main ()
{
	auto tests = readln.strip.to !(int);
	foreach (test; 0..tests)
	{
		auto s = readln.strip;
		writeln (solve (s));
	}
}
