Description

她想要求出对于 $k\in\{0,1,\dots,7\}$，$f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k\pmod 8]3^{\omega(i)}$ 的值。

上面的算式中，$\omega(i)$ 表示 $i$ 含有几种质因子，例如 $\omega(12)=\omega(6)=2,\omega(114514)=3$。

Input Format

仅一行，包含一个整数 $n$。

Output Format

共 $8$ 行，分别输出 $k=0,1,2,3,4,5,6,7$ 时 $f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k \pmod 8]3^{\omega(i)}$ 的值。

30

1
48
108
27
0
0
0
0

114514

1
32826
344727
1199826
1504818
538731
25515
0

Hint

【数据规模与约定】 |subtask|$n\le$|所占分值|时间限制| |:-:|:-:|:-:|:-:| |$1$|$100$|$10$|$500\texttt{ms}$| |$2$|$2\times10^6$|$20$|$1000\texttt{ms}$| |$3$|$3\times10^7$|$20$|$1000\texttt{ms}$| |$4$|$10^9$|$20$|$4000\texttt{ms}$| |$5$|$10^{10}$|$30$|$4000\texttt{ms}$|

如果你需要循环展开生成器，请前往附件下载。