#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<bits/stdc++.h>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<bitset>
// #include < unordered_map > 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include "boost/algorithm/string.hpp"
#define fio ios_base::sync_with_stdio(false)
#define mod 1000000007
#define mod1 mod
#define mod2 100000009
#define li long long int
#define ll int
#define readi(x) scanf("%d",&x)
#define  reads(x)  scanf("%s", x)
#define readl(x) scanf("%I64d",&x)
#define rep(i,n) for(i=0;i<n;i++)
#define revp(i,n) for(i=(n-1);i>=0;i--)
#define myrep1(i,a,b) for(i=a;i<=b;i++)
#define myrep2(i,a,b) for(i=b;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define MAXN 1000000000000000
#define MINN -1000000000000000000
#define pii pair<ll,ll> 
#define pdd pair<double,double>
#define pic pair<int,char>
#define N 400050
#define lgn 20
#define ddouble long double
#define minus minu
#define PI 3.1415926535
 
 
// #define INTMAX 200000000
 
// using namespace boost;
// #define si short int
 
using namespace std;
using namespace __gnu_pbds;             
typedef priority_queue<ll, vector<ll> > max_pq;
typedef priority_queue<char, vector<char> , greater<char >  > min_pq;
ll toint(const string &s) {stringstream ss; ss << s; ll x; ss >> x; return x;}
string tostring ( ll number ){stringstream ss; ss<< number; return ss.str();}
 
// typedef priority_queue<pair < ll , pair < pii , ll > >  , vector<pair < ll , pair < pii , ll > >  > ,greater<pair < ll , pair < pii , ll > >  > > min_pq;
 
typedef tree< ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update > OST;
typedef priority_queue< char , vector<char> > max_pqc;
// typedef priority_queue<ll, vector<ll > , greater < ll >  > min_pq;
 
// <<<MAIN BINARY SEARCH ON ANSWER BHUL KYUN JAATA HUN >>>
ll dp[ N ];
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
 
    dp[1] = 1;
    dp[2] = 3;
    for ( ll i = 3; i <= 100 ; i ++)
    {
    	ll min_moves=INT_MAX, optimalpick = 0;
    	for ( ll j = 2; j < i ; j ++)
    	{
    		if ( (dp[j-1]+dp[i-j]+2) < min_moves )
    		{
    			min_moves = (dp[j-1]+dp[i-j]+2);
    			optimalpick = j;
    		}
    	}
    	dp[i] = min_moves;
    	cout << dp[i] <<":" << optimalpick << endl;
    }
 
 
 
 
 
 
 
 
 
    //now u have the ans
 
 
 
 
 
 
 
}   
 
 
 

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgojaW5jbHVkZTxzdGFjaz4KI2luY2x1ZGU8cXVldWU+CiNpbmNsdWRlPGxpc3Q+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8Yml0c2V0PgovLyAjaW5jbHVkZSA8IHVub3JkZXJlZF9tYXAgPiAKI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgojaW5jbHVkZSA8ZXh0L3BiX2RzL3RyZWVfcG9saWN5LmhwcD4KLy8gI2luY2x1ZGUgImJvb3N0L2FsZ29yaXRobS9zdHJpbmcuaHBwIgojZGVmaW5lIGZpbyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKQojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgbW9kMSBtb2QKI2RlZmluZSBtb2QyIDEwMDAwMDAwOQojZGVmaW5lIGxpIGxvbmcgbG9uZyBpbnQKI2RlZmluZSBsbCBpbnQKI2RlZmluZSByZWFkaSh4KSBzY2FuZigiJWQiLCZ4KQojZGVmaW5lICByZWFkcyh4KSAgc2NhbmYoIiVzIiwgeCkKI2RlZmluZSByZWFkbCh4KSBzY2FuZigiJUk2NGQiLCZ4KQojZGVmaW5lIHJlcChpLG4pIGZvcihpPTA7aTxuO2krKykKI2RlZmluZSByZXZwKGksbikgZm9yKGk9KG4tMSk7aT49MDtpLS0pCiNkZWZpbmUgbXlyZXAxKGksYSxiKSBmb3IoaT1hO2k8PWI7aSsrKQojZGVmaW5lIG15cmVwMihpLGEsYikgZm9yKGk9YjtpPj1hO2ktLSkKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlYyBzZWNvbmQKI2RlZmluZSBNQVhOIDEwMDAwMDAwMDAwMDAwMDAKI2RlZmluZSBNSU5OIC0xMDAwMDAwMDAwMDAwMDAwMDAwCiNkZWZpbmUgcGlpIHBhaXI8bGwsbGw+IAojZGVmaW5lIHBkZCBwYWlyPGRvdWJsZSxkb3VibGU+CiNkZWZpbmUgcGljIHBhaXI8aW50LGNoYXI+CiNkZWZpbmUgTiA0MDAwNTAKI2RlZmluZSBsZ24gMjAKI2RlZmluZSBkZG91YmxlIGxvbmcgZG91YmxlCiNkZWZpbmUgbWludXMgbWludQojZGVmaW5lIFBJIDMuMTQxNTkyNjUzNQoKCi8vICNkZWZpbmUgSU5UTUFYIDIwMDAwMDAwMAoKLy8gdXNpbmcgbmFtZXNwYWNlIGJvb3N0OwovLyAjZGVmaW5lIHNpIHNob3J0IGludAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7ICAgICAgICAgICAgIAp0eXBlZGVmIHByaW9yaXR5X3F1ZXVlPGxsLCB2ZWN0b3I8bGw+ID4gbWF4X3BxOwp0eXBlZGVmIHByaW9yaXR5X3F1ZXVlPGNoYXIsIHZlY3RvcjxjaGFyPiAsIGdyZWF0ZXI8Y2hhciA+ICA+IG1pbl9wcTsKbGwgdG9pbnQoY29uc3Qgc3RyaW5nICZzKSB7c3RyaW5nc3RyZWFtIHNzOyBzcyA8PCBzOyBsbCB4OyBzcyA+PiB4OyByZXR1cm4geDt9CnN0cmluZyB0b3N0cmluZyAoIGxsIG51bWJlciApe3N0cmluZ3N0cmVhbSBzczsgc3M8PCBudW1iZXI7IHJldHVybiBzcy5zdHIoKTt9CgovLyB0eXBlZGVmIHByaW9yaXR5X3F1ZXVlPHBhaXIgPCBsbCAsIHBhaXIgPCBwaWkgLCBsbCA+ID4gICwgdmVjdG9yPHBhaXIgPCBsbCAsIHBhaXIgPCBwaWkgLCBsbCA+ID4gID4gLGdyZWF0ZXI8cGFpciA8IGxsICwgcGFpciA8IHBpaSAsIGxsID4gPiAgPiA+IG1pbl9wcTsKCnR5cGVkZWYgdHJlZTwgbGwsIG51bGxfdHlwZSwgbGVzczxsbD4sIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGUgPiBPU1Q7CnR5cGVkZWYgcHJpb3JpdHlfcXVldWU8IGNoYXIgLCB2ZWN0b3I8Y2hhcj4gPiBtYXhfcHFjOwovLyB0eXBlZGVmIHByaW9yaXR5X3F1ZXVlPGxsLCB2ZWN0b3I8bGwgPiAsIGdyZWF0ZXIgPCBsbCA+ICA+IG1pbl9wcTsKCi8vIDw8PE1BSU4gQklOQVJZIFNFQVJDSCBPTiBBTlNXRVIgQkhVTCBLWVVOIEpBQVRBIEhVTiA+Pj4KbGwgZHBbIE4gXTsKCgppbnQgbWFpbigpCnsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICAjaWZuZGVmIE9OTElORV9KVURHRQogICAgICAgIGZyZW9wZW4oImlucHV0LnR4dCIsInIiLHN0ZGluKTsKICAgICAgICBmcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KTsKICAgICNlbmRpZgoKICAgIGRwWzFdID0gMTsKICAgIGRwWzJdID0gMzsKICAgIGZvciAoIGxsIGkgPSAzOyBpIDw9IDEwMCA7IGkgKyspCiAgICB7CiAgICAJbGwgbWluX21vdmVzPUlOVF9NQVgsIG9wdGltYWxwaWNrID0gMDsKICAgIAlmb3IgKCBsbCBqID0gMjsgaiA8IGkgOyBqICsrKQogICAgCXsKICAgIAkJaWYgKCAoZHBbai0xXStkcFtpLWpdKzIpIDwgbWluX21vdmVzICkKICAgIAkJewogICAgCQkJbWluX21vdmVzID0gKGRwW2otMV0rZHBbaS1qXSsyKTsKICAgIAkJCW9wdGltYWxwaWNrID0gajsKICAgIAkJfQogICAgCX0KICAgIAlkcFtpXSA9IG1pbl9tb3ZlczsKICAgIAljb3V0IDw8IGRwW2ldIDw8IjoiIDw8IG9wdGltYWxwaWNrIDw8IGVuZGw7CiAgICB9CgoKCgoKCgoKCiAgICAvL25vdyB1IGhhdmUgdGhlIGFucwoKCgoKCgoKfSAgIAoKCiAgICAgICAg