#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, char st = ' ') {
	reverse(s.begin(),s.end());
	int n = s.size();
	vector<pair<int,string>> dp(n+1, {INT_MAX,""});
	dp[0] = {st != ' ', ""+st};

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

string s;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (auto [c, ss] : m) rm[ss] = c;
	
	{
		string t; cin >> t;
		for (char c : t) assert(m.count(c)), 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 (auto [c, ss] : m) {
		string t = s + ss;
		for (int i = s.size(); i < t.size(); i++) {
			{
			int j = i+1;
			int i = j-1;
			bool good = true;
			while (j < t.size()) {
				if (t[i] != t[j]) good = false;
				j++,i--;
			}
			if (good) build(t.substr(0, i+1), c);
			}
		}
		for (int i = s.size(); i < t.size(); i++) {
			{
			int j = i;
			int i = j;
			bool good = true;
			while (j < t.size()) {
				if (t[i] != t[j]) good = false;
				j++,i--;
			}
			if (good) build(t.substr(0, i+1), c);
			}
		}
	}

	if (!best) cout << "0\n";
	else cout << best << ' ' << ans << '\n';
}