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.