#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pii pair<int, int>
typedef int realInt;
#define int long long
#define ll long long
#define FOR(i,a,b) for (int i = a; i < b; ++i)
const double PI = acos(-1.0);
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const int N = 2e5+7;

#ifdef DBGLOCAL
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> bool operator!(const T_container& container) {return !container.size();}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() {cerr << endl;} void dbg_check() {cerr << endl;} int dbg_empty_check(int x) {return x;} string dbg_nested_idx;
template<typename T> int dbg_empty_check(const T& item) {if (!item) {return 0;} FOR(i, 0, N) {int out = dbg_empty_check(item[i]); if (out) { dbg_nested_idx += ' ' + to_string(i); return out;}} return 0;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
template<typename Head, typename... Tail> void dbg_check(Head H, Tail... T) { cerr << " ["; int out = dbg_empty_check(H); if(out) {reverse(dbg_nested_idx.begin(), dbg_nested_idx.end()); cerr << dbg_nested_idx << ": " << out; dbg_nested_idx.clear();} cerr << "]"; dbg_check(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define dbgarr(arr,n) cerr << "(" << #arr << "): "; FOR(_, 0, n) cerr << arr[_] << " \n"[_==n-1];
#define dbgcheck(...) cerr << "Arrays (" << #__VA_ARGS__ << "):", dbg_check(__VA_ARGS__)
#else
#define dbg(...)
#define dbgarr(arr,n)
#define dbgcheck(...)
#endif

#define ARRAYCHECK dbgcheck()
int check_palindrome(string s) {
    int n = s.size();
    FOR(i, 0, n) {
        if (s[i] != s[n-i-1]) {
            return 0;
        }
    }
    return 1;
}
void solve() {
    map<char, string> MORSE = {{'A',"01"},{'B',"1000"},{'C',"1010"},{'D',"100"},{'E',"0"},{'F',"0010"},{'G',"110"},{'H',"0000"},{'I',"00"},{'J',"0111"},{'K',"101"},{'L',"0100"},{'M',"11"},{'N',"10"},{'O',"111"},{'P',"0110"},{'Q',"1101"},{'R',"010"},{'S',"000"},{'T',"1"},{'U',"001"},{'V',"0001"},{'W',"011"},{'X',"1001"},{'Y',"1011"},{'Z',"1100"},{'0',"11111"},{'1',"01111"},{'2',"00111"},{'3',"00011"},{'4',"00001"},{'5',"00000"},{'6',"10000"},{'7',"11000"},{'8',"11100"},{'9',"11110"}};
    map<string, char> MORSE_INV;
    for(auto x : MORSE) {
        MORSE_INV.insert(mp(x.second, x.first));
    }
    string s;
    cin >> s;
    string morse;
    for (auto c : s) {
        morse += MORSE[c];
    }
    dbg(morse);
    int n = morse.size();
    set<string> palindromes;
    FOR(i, 0, n+1) {
        string add;
        FOR(j, 0, i) {
            add.push_back(morse[i-j-1]);
        }
        if (check_palindrome(morse + add)) {
            palindromes.insert(add);
        }
    }
    dbg(palindromes);
    string best_str;
    int best = INF;
    for(auto added : palindromes) {
        int sz = added.size();
        vector<int> dp(sz+1, INF);
        vector<string> dp_str(sz+1);
        dp[0] = 0;
        FOR(i, 1, sz+1) {
            FOR(j, 1, 6) {
                if (j > i) break;
                string curr = added.substr(i-j, j);
                if (!MORSE_INV.count(curr)) continue;
                if (dp[i-j]+1 < dp[i]) {
                    dp[i] = dp[i-j]+1;
                    dp_str[i] = dp_str[i-j] + MORSE_INV[curr];
                }
            }
        }
        if (dp[sz] < best) {
            best = dp[sz];
            best_str = dp_str[sz];
        }
        // dbg(added, dp, dp_str);
    }
    cout << best << ' ' << best_str << '\n';
}

realInt main() {
    std::cout << fixed;
    std::cout << std::setprecision(10);
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0); std::cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {solve(); ARRAYCHECK;}
    return 0;
}