#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)
int a[19][19], H, W, maxn = 0;
bool check(int px, int py) {
int dx[9] = { -1, -1, -1, 0, 1, 1, 1, 0, 0 };
int dy[9] = { -1, 0, 1, 1, 1, 0, -1, -1, 0 };
for (int i = 0; i < 9; i++) {
int ex = px + dx[i], ey = py + dy[i];
if (ex < 0 || ey < 0 || ex >= H || ey >= W) continue;
if (a[ex][ey] == 1) return false;
}
return true;
}
void dfs(int dep, pair<int, int> L) {
maxn = max(maxn, dep);
for (int i = 0; i < H - 1; i++) {
for (int j = 0; j < W; j++) {
if (make_pair(i, j) <= L) continue;
bool I1 = check(i, j);
bool I2 = check(i + 1, j);
if (I1 == true && I2 == true) {
a[i][j] = 1; a[i + 1][j] = 1;
dfs(dep + 1, make_pair(i, j));
a[i][j] = 0; a[i + 1][j] = 0;
}
}
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W - 1; j++) {
if (make_pair(i, j) <= L) continue;
bool I1 = check(i, j);
bool I2 = check(i, j + 1);
if (I1 == true && I2 == true) {
a[i][j] = 1; a[i][j + 1] = 1;
dfs(dep + 1, make_pair(i, j));
a[i][j] = 0; a[i][j + 1] = 0;
}
}
}
}
int main() {
for (int i = 1; i <= 15; i++) {
for (int j = 1; j <= 15; j++) {
if (i*j > 44) continue;
H = i; W = j; maxn = 0;
dfs(0, make_pair(-1, -1));
printf("% 3d", maxn);
}
cout << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojcHJhZ21hIHdhcm5pbmcgKGRpc2FibGU6IDQ5OTYpCgppbnQgYVsxOV1bMTldLCBILCBXLCBtYXhuID0gMDsKCmJvb2wgY2hlY2soaW50IHB4LCBpbnQgcHkpIHsKCWludCBkeFs5XSA9IHsgLTEsIC0xLCAtMSwgMCwgMSwgMSwgMSwgMCwgMCB9OwoJaW50IGR5WzldID0geyAtMSwgMCwgMSwgMSwgMSwgMCwgLTEsIC0xLCAwIH07Cglmb3IgKGludCBpID0gMDsgaSA8IDk7IGkrKykgewoJCWludCBleCA9IHB4ICsgZHhbaV0sIGV5ID0gcHkgKyBkeVtpXTsKCQlpZiAoZXggPCAwIHx8IGV5IDwgMCB8fCBleCA+PSBIIHx8IGV5ID49IFcpIGNvbnRpbnVlOwoJCWlmIChhW2V4XVtleV0gPT0gMSkgcmV0dXJuIGZhbHNlOwoJfQoJcmV0dXJuIHRydWU7Cn0KCnZvaWQgZGZzKGludCBkZXAsIHBhaXI8aW50LCBpbnQ+IEwpIHsKCW1heG4gPSBtYXgobWF4biwgZGVwKTsKCglmb3IgKGludCBpID0gMDsgaSA8IEggLSAxOyBpKyspIHsKCQlmb3IgKGludCBqID0gMDsgaiA8IFc7IGorKykgewoJCQlpZiAobWFrZV9wYWlyKGksIGopIDw9IEwpIGNvbnRpbnVlOwoJCQlib29sIEkxID0gY2hlY2soaSwgaik7CgkJCWJvb2wgSTIgPSBjaGVjayhpICsgMSwgaik7CgoJCQlpZiAoSTEgPT0gdHJ1ZSAmJiBJMiA9PSB0cnVlKSB7CgkJCQlhW2ldW2pdID0gMTsgYVtpICsgMV1bal0gPSAxOwoJCQkJZGZzKGRlcCArIDEsIG1ha2VfcGFpcihpLCBqKSk7CgkJCQlhW2ldW2pdID0gMDsgYVtpICsgMV1bal0gPSAwOwoJCQl9CgkJfQoJfQoKCWZvciAoaW50IGkgPSAwOyBpIDwgSDsgaSsrKSB7CgkJZm9yIChpbnQgaiA9IDA7IGogPCBXIC0gMTsgaisrKSB7CgkJCWlmIChtYWtlX3BhaXIoaSwgaikgPD0gTCkgY29udGludWU7CgkJCWJvb2wgSTEgPSBjaGVjayhpLCBqKTsKCQkJYm9vbCBJMiA9IGNoZWNrKGksIGogKyAxKTsKCgkJCWlmIChJMSA9PSB0cnVlICYmIEkyID09IHRydWUpIHsKCQkJCWFbaV1bal0gPSAxOyBhW2ldW2ogKyAxXSA9IDE7CgkJCQlkZnMoZGVwICsgMSwgbWFrZV9wYWlyKGksIGopKTsKCQkJCWFbaV1bal0gPSAwOyBhW2ldW2ogKyAxXSA9IDA7CgkJCX0KCQl9Cgl9Cn0KCmludCBtYWluKCkgewoJZm9yIChpbnQgaSA9IDE7IGkgPD0gMTU7IGkrKykgewoJCWZvciAoaW50IGogPSAxOyBqIDw9IDE1OyBqKyspIHsKCQkJaWYgKGkqaiA+IDQ0KSBjb250aW51ZTsKCQkJSCA9IGk7IFcgPSBqOyBtYXhuID0gMDsKCQkJZGZzKDAsIG1ha2VfcGFpcigtMSwgLTEpKTsKCQkJcHJpbnRmKCIlIDNkIiwgbWF4bik7CgkJfQoJCWNvdXQgPDwgZW5kbDsKCX0KCXJldHVybiAwOwp9