#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=