#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define int long long

const int n = 50;
int dp[n][n];

void solve() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = 1e9;
        }
    }
    for (int i = 1; i < n; ++i) {
        dp[0][i] = 0;
        dp[i][0] = 0;
        dp[1][i] = i;
        dp[i][1] = i;
    }
    for (int a = 2; a < n; ++a) {
        for (int b = 2; b < n; ++b) {
            for (int y = 0; y <= b; ++y) {
                for (int x1 = 0; x1 <= a; ++x1) {
                    for (int x2 = 0; x2 <= a; ++x2) {
                        dp[a][b] = min(
                            dp[a][b],
                            dp[x1][y] + dp[a - x1][y] + dp[x2][b - y] + dp[a - x2][b - y]
                        );
                    }
                }
            }
            if (a == b) {
                cout << a << ": " << dp[a][a] << '\n';
                dp[a][a] = 1;
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    solve();
}