task689

#define loop(i,from,to) for (int i = from; i < to; ++i)
#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::tuple;
using std::set;

const int INF = 1e9+7;
const double eps = 1e-6;

template <typename T> void reverse(T &a) {
  long long s = a.size();
  for (long long i = 0; i < s / 2; ++i)
    std::swap(a[i], a[s - i - 1]);
}

string transform(string s, int base) {
  int n = std::stoi(s), x;
  string mod;
  while (n >= base) {
    x = n % base;
    if (x >= 10) mod.push_back((char)('A' + x - 10));
    else mod.push_back(char(x + '0'));
    n /= base;
  }
  if (n >= 10) mod.push_back((char)('A' + n - 10));
  else mod.push_back(char(n + '0'));
  reverse(mod);
  return mod;
}

int amount(string s) {
  set<char> A;
  for (int i = 0; i < s.length(); ++i)
    A.insert(s[i]);
  return A.size();
}


signed main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  string pta, s, mx;
  int mxBase;
  for (int i = 0; i < n; ++i) {
    cin >> pta;
    for (int base = 2; base <= 36; ++base) {
      s = transform(pta, base);
      if ((s.length() + amount(s)) < (pta.length() + amount(pta))) {
        mx = s;
        mxBase = base;
      }
    }
    cout << mxBase << " " << mx << endl;
  }
  //std::cout << "Hello World!\n";
  return 0;
}