20596번 - Hardcore String Counting 2 다국어

문제

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.

제한

힌트

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