package main

import (
	"fmt"
)

const maxn int = 1000*1000*1000;
const maxw int = 22;


func wordCounts(p []int, max int) []int {
	n := len(p);

	var dim int = 2;
	var wd, pow, ct int;

	dat := make([][]int, max);
	cts := make([]int, max);
	for i := 0; i < max; i++ {
		dat[i] = make([]int, dim);
		dim *= 2;
	}

	dim = 2;
	for i := 0; i < max; i++ {
		ct = 0;
		// count pre-known exclusions
		if i>0 {
			for j :=0; j<dim; j++ {
				if dat[i][j]==2 {
					ct +=1;
				}
			}
		}

		// write down known words
		for j := 0; j < n-i-1; j++ {
			wd = 0; pow = 1;
			for k := 0; k < i+1; k++ {
				wd += pow*p[j+i-k]
				pow *= 2;
			}
			if dat[i][wd] == 0 {
				ct += 1;
				dat[i][wd] = 1;
			}
			//search finishes early
			if ct == dim {
				break
			}
		}
		//extract counts: cts[i] = dim - ct
		//write down next level exclusions
		for j := 0; j < dim; j++ {
			if dat[i][j]==0  {
				cts[i]+=1;
			}
			if dat[i][j]==0 || dat[i][j]==2  {

				if i < max-1 {
					dat[i+1][j]= 2;
					dat[i+1][j+dim]=2;
					dat[i+1][2*j]=2;
					dat[i+1][2*j+1]=2;
				}
			}

		}
		dim *= 2;
	}

	return cts
}


func paritySeq(n int) []int {

	b := make([]int, n+1);
	copy(b, []int{0, 1});

	for i:=2; i < n+1; i++ {
		b[i] = i-b[b[i-2]];
	};

	for i:=0; i < n+1; i++ {
		b[i] = b[i]%2;
	};

	return b
}


func main() {

	p := paritySeq(maxn);

	//fmt.Println(p[0:30]);

	fmt.Println(wordCounts(p,maxw));


}