#include "bits/stdc++.h"
using namespace std;

map<char,string> m{
	{'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> rm;

int best = INT_MAX;
string ans = "";
void build(string s) {
	reverse(s.begin(),s.end());
	int n = s.size();
	vector<pair<int,string>> dp(n+1, {INT_MAX,""});
	dp[0] = {0, ""};

	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= 5; j++) {
			if (i+j > n) break;
			string t = s.substr(i,j);
			if (rm.count(t)) {
				dp[i+j] = min(dp[i+j], {dp[i].first+1, dp[i].second+rm[t]});
			}
		}
	}
	if (dp[n].first < best) {
		best = dp[n].first;
		ans = dp[n].second;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (auto [c, s] : m) {
		assert(!rm.count(s));
		rm[s] = c;
	}
	
	string s;
	{
		string t; cin >> t;
		for (char c : t) s += m[c];
	}
	int n = s.size();

	for (int i = (n-1)/2; i < n; i++) {
		{
		int j = i+1;
		int i = j-1;
		bool good = true;
		while (j < n) {
			if (s[i] != s[j]) good = false;
			j++,i--;
		}
		if (good) build(s.substr(0, i+1));
		}
	}
	for (int i = n/2; i < n; i++) {
		{
		int j = i;
		int i = j;
		bool good = true;
		while (j < n) {
			if (s[i] != s[j]) good = false;
			j++,i--;
		}
		if (good) build(s.substr(0, i+1));
		}
	}

	for (int i = 0; i < 32; i++) {
		string t = s;
		for (int j = i; j; j /= 2) {
			t += '0' + (j&1);
		}
		build(t);
	}

	cout << best << ' ' << ans << '\n';
}