#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pl pair<ll, ll>
#define pi pair<int, int>
#define minpq priority_queue<ll, vector<ll>, greater<ll>>
using namespace std;

#if 1
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '['; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "]";}
void _print() {cerr << endl << flush;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "*["<<__LINE__<<"]\t"<< #x << " = "; _print(x)
#endif

const ll mod = 1e9 + 7;

template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll gcd(ll a, ll b) {if(b == 0){return a;} return gcd(b, a % b);}

const int inf = 1 << 30;
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	map<char, string> mp;
	mp['A'] = "01";
	mp['B'] = "1000";
	mp['C'] = "1010";
	mp['D'] = "100";
	mp['E'] = "0";
	mp['F'] = "0010";
	mp['G'] = "110";
	mp['H'] = "0000";
	mp['I'] = "00";
	mp['J'] = "0111";
	mp['K'] = "101";
	mp['L'] = "0100";
	mp['M'] = "11";
	mp['N'] = "10";
	mp['O'] = "111";
	mp['P'] = "0110";
	mp['Q'] = "1101";
	mp['R'] = "010";
	mp['S'] = "000";
	mp['T'] = "1";
	mp['U'] = "001";
	mp['V'] = "0001";
	mp['W'] = "011";
	mp['X'] = "1001";
	mp['Y'] = "1011";
	mp['Z'] = "1100";
	mp['0'] = "11111";
	mp['1'] = "01111";
	mp['2'] = "00111";
	mp['3'] = "00011";
	mp['4'] = "00001";
	mp['5'] = "00000";
	mp['6'] = "10000";
	mp['7'] = "11000";
	mp['8'] = "11100";
	mp['9'] = "11110";
	string s; cin >> s;
	string ms = "";
	for (int i = 0; i < s.size(); i ++) if ((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= '0' && s[i] <= '9'))ms += mp[s[i]];
	//debug(ms);
	int ans = inf; string add = "";
	for (int len = ms.size(); len >= 0; len --){
		bool good = true;
		for (int x = 0; len + x < ms.size(); x ++){
			if (len - 1 - x < 0 || ms[len + x] != ms[len - 1 - x]) good = false;
		}
		if (! good) continue;
		string cur = ms.substr(0, len - (ms.size() - len));
		//debug(cur);
		if (cur.size() == 0){
			ans = 0; add = ""; break;
		}
		//debug(cur);
		reverse(cur.begin(), cur.end());
		vector<pair<int, string>> dp(cur.size(), {inf, ""});
		for (int i = 0; i < cur.size(); i ++){
			for (auto p : mp){
				if (cur.substr(0, i + 1) == p.se){
					dp[i].fi = 1; dp[i].se = ""; dp[i].se.push_back(p.fi);
				}
			}
			for (int j = 0; j < i; j ++){
				for (auto p : mp){
					if (cur.substr(j + 1, i - j) == p.se && dp[j].fi + 1 < dp[i].fi){
						dp[i].fi = dp[j].fi + 1; dp[i].se = dp[j].se; dp[i].se.push_back(p.fi);
					}
				}
			}
		}
		if (dp.back().fi < ans){
			ans = dp.back().fi; add = dp.back().se;
		}
	}
	for (int pos = ms.size() - 1; pos >= 0; pos --){
		bool good = true;
		for (int x = 1; pos + x < ms.size(); x ++){
			if (pos - x < 0 || ms[pos + x] != ms[pos - x]) good = false;
		}
		if (! good) continue;
		string cur = ms.substr(0, pos - (ms.size() - 1 - pos));
		//debug(cur);
		if (cur.size() == 0){
			ans = 0; add = ""; break;
		}
		reverse(cur.begin(), cur.end());
		//debug(cur);
		vector<pair<int, string>> dp(cur.size(), {inf, ""});
		for (int i = 0; i < cur.size(); i ++){
			for (auto p : mp){
				if (cur.substr(0, i + 1) == p.se){
					dp[i].fi = 1; dp[i].se = ""; dp[i].se.push_back(p.fi);
				}
			}
			for (int j = 0; j < i; j ++){
				for (auto p : mp){
					if (cur.substr(j + 1, i - j) == p.se && dp[j].fi + 1 < dp[i].fi){
						dp[i].fi = dp[j].fi + 1; dp[i].se = dp[j].se; dp[i].se.push_back(p.fi);
					}
				}
			}
		}
		if (dp.back().fi < ans){
			ans = dp.back().fi; add = dp.back().se;
		}
	}
	cout << ans << ' ' << add << '\n';
}