#include <bits/stdc++.h>

using namespace std;

int sum[100];

int main()
{
	for (int L = 4; L <= 20; L++) {
		int cnt = 0;
		for (int i = 0; i < (1 << L); i++) {
			string str = "";
			for (int j = 0; j < L; j++) {
				str += char('0' + ((i >> j) & 1));
			}
			for (int i = 1; i <= L; i++) sum[i] = 0;
			for (int i = 1; i <= L; i++) {
				int flag = 1;
				for (int k = 1; i + k + k - 1 <= L; k++) {
					if (str.substr(i - 1, k) == str.substr(i + k - 1, k)) {
						flag = 0;
						break;
					}
				}
				if (flag) {
					for (int j = i; j <= L; j++) sum[j]++;
				}
			}
			int check = 1;
			for (int i = 1; i <= L; i++) check &= 2 * sum[i] >= i;
			if (check) {
				cnt++;
			}
		}
		cout << L << ' ' << cnt << endl;
	}
	return 0;
}
