#include <iostream>
using namespace std;
int tileways(int n) //n=no.of columns of the rectangle.
{
int l[20];//straight border
int L[20];//extra square
l[0] = 1;
l[1] = 1;
L[0] = 0;
L[1] = 1;
for (int i = 2; i <=n; i++) {
l[i] = l[i-1] + l[i-2] + 2*L[i-2];
L[i] = l[i-1] + L[i-1];
}
return l[n];
}
int main() {
for (int i = 1; i < 10; i++)
std::cout<<i<<" "<< tileways(i)<<std::endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IHRpbGV3YXlzKGludCBuKSAvL249bm8ub2YgY29sdW1ucyBvZiB0aGUgcmVjdGFuZ2xlLgp7CiAgICBpbnQgbFsyMF07Ly9zdHJhaWdodCBib3JkZXIKICAgIGludCBMWzIwXTsvL2V4dHJhIHNxdWFyZQogICAgbFswXSA9IDE7IAogICAgbFsxXSA9IDE7CiAgICBMWzBdID0gMDsKICAgIExbMV0gPSAxOwogICAgZm9yIChpbnQgaSA9IDI7IGkgPD1uOyBpKyspIHsKICAgICAgICBsW2ldID0gbFtpLTFdICsgbFtpLTJdICsgMipMW2ktMl07CiAgICAgICAgTFtpXSA9IGxbaS0xXSArIExbaS0xXTsKICAgIH0KICAgIHJldHVybiBsW25dOwp9CgppbnQgbWFpbigpIHsKCWZvciAoaW50IGkgPSAxOyBpIDwgMTA7IGkrKykgCgkJc3RkOjpjb3V0PDxpPDwiICI8PCB0aWxld2F5cyhpKTw8c3RkOjplbmRsOwoJcmV0dXJuIDA7Cn0=