#pragma GCC Optimize("Ofast")
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)

using namespace std;
using ll = long long;

const bool TEST = true;


string BAD;

string solveEq(char first, map<char, int> mp, int n) {
  mp[first] -= 2;
  vector<pair<char, int>> tmp(all(mp));
  string ans = "";
  ans.reserve(n);
  ans.push_back(first);
  ans.push_back(first);
  string buffer;

  for (auto& [k, v] : tmp) {
    if (k == first) continue;
    while (v--) {
      buffer.push_back(k);
    }
  }

  int x = mp[first];

  if (x > buffer.size()) {
    return BAD;
  }

  int pos = 0;
  for (int i = 0; i < buffer.size(); i++) {
    if (buffer[i] < first) {
      int rem = buffer.size() - i;
      if (rem > x) {
        ans.push_back(buffer[i]);
      } else {
        while (i < buffer.size()) {
          ans.push_back(buffer[i++]);
          ans.push_back(first);
        }
        assert(ans.size() == n);
        return ans;
      }
    } else {
      if (i == 0) {
        while (i < buffer.size()) {
          ans.push_back(buffer[i++]);
          if (x > 0) {
            ans.push_back(first);
            x--;
          }
        }
        assert(x == 0);
        return ans;
      } else {
        while (i < buffer.size()) {
          if (x > 0) {
            ans.push_back(first);
            x--;
          }
          ans.push_back(buffer[i++]);
        }
        assert(x == 0);
        return ans;
      }
    }
  }

  return ans;
}

string build(char first, char second, map<char, int> mp, int n) {
  if (first != second) {
    mp[first]--;
    mp[second]--;
    if (mp[first] == 0) mp.erase(mp.find(first));
    if (mp[second] == 0) mp.erase(mp.find(second));


    vector<pair<char, int>> tmp(all(mp));
    bool kek = false;
    for (int i = 0; i + 1 < tmp.size(); i++) {
      if (tmp[i].first == first && tmp[i + 1].first == second) {
        if (i + 2 < tmp.size()) {
          kek = true;
          break;
        } else {
          swap(tmp[i], tmp[i + 1]);
          break;
        }
      }
    }

    string ans = "";
    ans.reserve(n);
    ans.push_back(first);
    ans.push_back(second);

    for (int i = 0; i < tmp.size(); i++) {
      auto [k, v] = tmp[i];
      if (k == second && kek) {
        ans.push_back(tmp[i + 1].first);
        tmp[i + 1].second--;
      }
      for (int itr = 0; itr < v; itr++) {
        ans.push_back(k);
      }
    }
    return ans;
  } else {
    return solveEq(first, mp, n);
  }
}

string solve(string s) {
  const int n = s.size();
  sort(all(s));

  map<char, int> cnt;
  for (char ch : s) cnt[ch]++;

  bool hasUn = false;
  for (auto& [k, v] : cnt) {
    if (v == 1) {
      auto mp = cnt;
      mp[k]--;

      string ans = "";
      ans.push_back(k);
      for (auto& [key, val] : mp) {
        while (val--) {
          ans.push_back(key);
        }
      }
      return ans;

    }
  }

  string answer = s;
  reverse(all(answer));
  BAD = answer;

  for (auto [k1, v1] : cnt) {
    for (auto [k2, _] : cnt) {
      if (k1 != k2 || v1 > 1) {
        auto res = build(k1, k2, cnt, n);
        assert(res.size() == n);
        if (res < answer) {
          answer = res;
        }
      }
    }
  }
  return answer;
}


int Calc(string& s) {
  int n = s.size();
  for (int i = 1; i + 1 < n; i++) {
    if (s[i] == s[0] && s[i + 1] == s[1]) return 2;
  }
  for (int i = 1; i < n; i++) {
    if (s[i] == s[0]) return 1;
  }
  return 0;
}

string brute(string s) {
  sort(all(s));
  string best = s;
  reverse(all(best));
  int cnt = s.size();
  do {
    int cur = Calc(s);
    if (cur < cnt) {
      cnt = cur;
      best = s;
    } else if (cur == cnt) {
      best = min(best, s);
    }
  } while (next_permutation(all(s)));
  return best;
}

string gen(int n) {
  string ans(n, 'a');
  for (int i = 0; i < n; i++) {
    ans[i] += rand() % 5;
  }
  return ans;
}

void Test() {
  while (true) {
    int n = 6;
    string f = gen(n);

    string a = solve(f);
    string b = brute(f);


    if (a != b) {
      cout << f << ' ' << a << ' ' << b << endl;
    }

    assert(a == b);

  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  if (TEST) {
    cin >> t;
  } else {
    t = 1;
  }

  //Test();

  while (t--) {
    string s;
    cin >> s;
    cout << solve(s) << '\n';
  }
}