“Hardcore String Counting 1” 发生了什么？那是个秘密！

如果一个字母表上的非空单词 $v$ 可以表示为 $v = ww$（其中 $w$ 为某个单词），则称其为平方串（square）。

如果一个单词的所有非空子串都不是平方串，则称该单词为无平方串（square-free）。

你的任务是计算对于每个从 $1$ 到 $n$ 的 $\ell$，字母表 $\{\mathtt{a}, \mathtt{b}, \mathtt{c}\}$ 上长度为 $\ell$ 的无平方串的数量。

输入仅包含一行，为一个整数 $n$ ($1 \le n \le 120$)。

对于每个从 $1$ 到 $n$ 的 $\ell$，在单独的一行中输出字母表 $\{\mathtt{a}, \mathtt{b}, \mathtt{c}\}$ 上长度为 $\ell$ 的无平方串的数量。

样例

输入格式 1

10

输出格式 1

3
6
12
18
30
42
60
78
108
144

说明

你可以查看 https://oeis.org/A006156 以获取更多详细信息，但这可能对你帮助不大。