#include <algorithm>
#include <iostream>
#include <random>
#include <map>
using namespace std;
random_device rd;
mt19937 rng(rd());
uniform_int_distribution<int> d4(0,3), d10(0,9);
int state[4][4];
void reset() { for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) state[r][c]=0; }
bool is_game_over() {
for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) if (state[r][c]==0) return false;
for (int r=0; r<4; ++r) for (int c=0; c<3; ++c) if (state[r][c]==state[r][c+1]) return false;
for (int r=0; r<3; ++r) for (int c=0; c<4; ++c) if (state[r][c]==state[r+1][c]) return false;
return true;
}
void get_random_empty_cell(int &r, int &c) {
r=-1; c=-1;
int seen = 0;
for (int rr=0; rr<4; ++rr) for (int cc=0; cc<4; ++cc) if (state[rr][cc]==0) ++seen;
if (!seen) return;
while (true) { r=d4(rng); c=d4(rng); if (state[r][c]==0) return; }
}
bool add_random_cell() {
int r, c; get_random_empty_cell(r,c);
if (r==-1) return false;
state[r][c] = ( d10(rng)==0 ? 4 : 2 );
return true;
}
bool compress(int *row) {
int tmp[4], dal=0, hlp[4], bol=0;
bool change = false;
for (int i=0; i<4; ++i) if (row[i]) tmp[dal++]=row[i];
for (int i=0; i<4; ++i) hlp[i]=0;
for (int i=0; i<dal; ) { if (i+1<dal && tmp[i]==tmp[i+1]) { hlp[bol++]=2*tmp[i]; i+=2; } else { hlp[bol++]=tmp[i]; i+=1; } }
for (int i=0; i<4; ++i) if (row[i]!=hlp[i]) change = true;
for (int i=0; i<4; ++i) row[i]=hlp[i];
return change;
}
bool move1(int r0, int c0, int dr, int dc) {
int tmp[4];
for (int i=0; i<4; ++i) tmp[i]=state[r0+i*dr][c0+i*dc];
bool change = compress(tmp);
for (int i=0; i<4; ++i) state[r0+i*dr][c0+i*dc]=tmp[i];
return change;
}
void move(int d) {
bool change = false;
if (d==0) for (int c=0; c<4; ++c) change |= move1(0,c, 1,0);
if (d==1) for (int c=0; c<4; ++c) change |= move1(3,c,-1,0);
if (d==2) for (int r=0; r<4; ++r) change |= move1(r,0,0, 1);
if (d==3) for (int r=0; r<4; ++r) change |= move1(r,3,0,-1);
if (change) add_random_cell();
}
int game() {
reset();
add_random_cell();
add_random_cell();
while (!is_game_over()) move( d4(rng) );
int answer = 0;
for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) answer = max( answer, state[r][c] );
return answer;
}
int main() {
map<int,int> stats;
long long games; cin >> games;
while (--games) ++stats[ game() ];
for (auto tmp:stats) cout << tmp.first << ": " << tmp.second << endl;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8bWFwPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKcmFuZG9tX2RldmljZSByZDsKbXQxOTkzNyBybmcocmQoKSk7CnVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxpbnQ+IGQ0KDAsMyksIGQxMCgwLDkpOwoKaW50IHN0YXRlWzRdWzRdOwoKdm9pZCByZXNldCgpIHsgZm9yIChpbnQgcj0wOyByPDQ7ICsrcikgZm9yIChpbnQgYz0wOyBjPDQ7ICsrYykgc3RhdGVbcl1bY109MDsgfQoKYm9vbCBpc19nYW1lX292ZXIoKSB7CiAgICBmb3IgKGludCByPTA7IHI8NDsgKytyKSBmb3IgKGludCBjPTA7IGM8NDsgKytjKSBpZiAoc3RhdGVbcl1bY109PTApIHJldHVybiBmYWxzZTsKICAgIGZvciAoaW50IHI9MDsgcjw0OyArK3IpIGZvciAoaW50IGM9MDsgYzwzOyArK2MpIGlmIChzdGF0ZVtyXVtjXT09c3RhdGVbcl1bYysxXSkgcmV0dXJuIGZhbHNlOwogICAgZm9yIChpbnQgcj0wOyByPDM7ICsrcikgZm9yIChpbnQgYz0wOyBjPDQ7ICsrYykgaWYgKHN0YXRlW3JdW2NdPT1zdGF0ZVtyKzFdW2NdKSByZXR1cm4gZmFsc2U7CiAgICByZXR1cm4gdHJ1ZTsKfQoKdm9pZCBnZXRfcmFuZG9tX2VtcHR5X2NlbGwoaW50ICZyLCBpbnQgJmMpIHsKICAgIHI9LTE7IGM9LTE7CiAgICBpbnQgc2VlbiA9IDA7CiAgICBmb3IgKGludCBycj0wOyBycjw0OyArK3JyKSBmb3IgKGludCBjYz0wOyBjYzw0OyArK2NjKSBpZiAoc3RhdGVbcnJdW2NjXT09MCkgKytzZWVuOwogICAgaWYgKCFzZWVuKSByZXR1cm47CiAgICB3aGlsZSAodHJ1ZSkgeyByPWQ0KHJuZyk7IGM9ZDQocm5nKTsgaWYgKHN0YXRlW3JdW2NdPT0wKSByZXR1cm47IH0KfQoKYm9vbCBhZGRfcmFuZG9tX2NlbGwoKSB7CiAgICBpbnQgciwgYzsgZ2V0X3JhbmRvbV9lbXB0eV9jZWxsKHIsYyk7CiAgICBpZiAocj09LTEpIHJldHVybiBmYWxzZTsKICAgIHN0YXRlW3JdW2NdID0gKCBkMTAocm5nKT09MCA/IDQgOiAyICk7CiAgICByZXR1cm4gdHJ1ZTsKfQoKYm9vbCBjb21wcmVzcyhpbnQgKnJvdykgewogICAgaW50IHRtcFs0XSwgZGFsPTAsIGhscFs0XSwgYm9sPTA7CiAgICBib29sIGNoYW5nZSA9IGZhbHNlOwogICAgZm9yIChpbnQgaT0wOyBpPDQ7ICsraSkgaWYgKHJvd1tpXSkgdG1wW2RhbCsrXT1yb3dbaV07CiAgICBmb3IgKGludCBpPTA7IGk8NDsgKytpKSBobHBbaV09MDsKICAgIGZvciAoaW50IGk9MDsgaTxkYWw7ICkgeyBpZiAoaSsxPGRhbCAmJiB0bXBbaV09PXRtcFtpKzFdKSB7IGhscFtib2wrK109Mip0bXBbaV07IGkrPTI7IH0gZWxzZSB7IGhscFtib2wrK109dG1wW2ldOyBpKz0xOyB9IH0KICAgIGZvciAoaW50IGk9MDsgaTw0OyArK2kpIGlmIChyb3dbaV0hPWhscFtpXSkgY2hhbmdlID0gdHJ1ZTsKICAgIGZvciAoaW50IGk9MDsgaTw0OyArK2kpIHJvd1tpXT1obHBbaV07CiAgICByZXR1cm4gY2hhbmdlOwp9Cgpib29sIG1vdmUxKGludCByMCwgaW50IGMwLCBpbnQgZHIsIGludCBkYykgewogICAgaW50IHRtcFs0XTsKICAgIGZvciAoaW50IGk9MDsgaTw0OyArK2kpIHRtcFtpXT1zdGF0ZVtyMCtpKmRyXVtjMCtpKmRjXTsKICAgIGJvb2wgY2hhbmdlID0gY29tcHJlc3ModG1wKTsKICAgIGZvciAoaW50IGk9MDsgaTw0OyArK2kpIHN0YXRlW3IwK2kqZHJdW2MwK2kqZGNdPXRtcFtpXTsKICAgIHJldHVybiBjaGFuZ2U7Cn0KCnZvaWQgbW92ZShpbnQgZCkgewogICAgYm9vbCBjaGFuZ2UgPSBmYWxzZTsKICAgIGlmIChkPT0wKSBmb3IgKGludCBjPTA7IGM8NDsgKytjKSBjaGFuZ2UgfD0gbW92ZTEoMCxjLCAxLDApOwogICAgaWYgKGQ9PTEpIGZvciAoaW50IGM9MDsgYzw0OyArK2MpIGNoYW5nZSB8PSBtb3ZlMSgzLGMsLTEsMCk7CiAgICBpZiAoZD09MikgZm9yIChpbnQgcj0wOyByPDQ7ICsrcikgY2hhbmdlIHw9IG1vdmUxKHIsMCwwLCAxKTsKICAgIGlmIChkPT0zKSBmb3IgKGludCByPTA7IHI8NDsgKytyKSBjaGFuZ2UgfD0gbW92ZTEociwzLDAsLTEpOwogICAgaWYgKGNoYW5nZSkgYWRkX3JhbmRvbV9jZWxsKCk7Cn0KCmludCBnYW1lKCkgewogICAgcmVzZXQoKTsKICAgIGFkZF9yYW5kb21fY2VsbCgpOwogICAgYWRkX3JhbmRvbV9jZWxsKCk7CiAgICB3aGlsZSAoIWlzX2dhbWVfb3ZlcigpKSBtb3ZlKCBkNChybmcpICk7CiAgICBpbnQgYW5zd2VyID0gMDsKICAgIGZvciAoaW50IHI9MDsgcjw0OyArK3IpIGZvciAoaW50IGM9MDsgYzw0OyArK2MpIGFuc3dlciA9IG1heCggYW5zd2VyLCBzdGF0ZVtyXVtjXSApOwogICAgcmV0dXJuIGFuc3dlcjsKfQoKaW50IG1haW4oKSB7CiAgICBtYXA8aW50LGludD4gc3RhdHM7CiAgICBsb25nIGxvbmcgZ2FtZXM7IGNpbiA+PiBnYW1lczsKICAgIHdoaWxlICgtLWdhbWVzKSArK3N0YXRzWyBnYW1lKCkgXTsKICAgIGZvciAoYXV0byB0bXA6c3RhdHMpIGNvdXQgPDwgdG1wLmZpcnN0IDw8ICI6ICIgPDwgdG1wLnNlY29uZCA8PCBlbmRsOwp9