#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;

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

int amount(const 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;
  for (int i = 0; i < n; ++i) {
    cin >> pta;
    int mn = 1e9 + 7;
    int mnBase = 0;
    string ans = pta;

    for (int base = 2; base <= 36; ++base) {
      s = transform(pta, base);
      if ( s.length() + amount(s) < mn) {
        mn = s.length() + amount(s);
        mnBase = base;
        ans = s;
      }
    }
    cout << mnBase << " " << ans << endl;
  }
  return 0;
}