시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

What happened to "Hardcore String Counting 1"? That's a secret!

A non-empty word $v$ over some alphabet is a square if it can be represented as $v = ww$ for some word $w$.

A word is square-free if all its non-empty substrings are not squares.

Your task is to compute the number of square-free words of length $\ell$ over the alphabet {a, b, c} for each $\ell$ from $1$ to $n$.

입력

The only line of the input contains an integer $n$ ($1 \leq n \leq 120$).

출력

For each $\ell$ from $1$ to $n$, print the number of square-free words of length $\ell$ over the alphabet {a, b, c} on a separate line.

예제 입력 1

10

예제 출력 1

3
6
12
18
30
42
60
78
108
144

힌트

You can see https://oeis.org/A006156 for more details, but this probably won't help you much.