题目背景

Bessie 和大家正坐在刚刚合并完成的牛棚里，跟着 Farmer John 在一起学习循环展开。

Farmer John 说，如果一个循环展开的步长为 $8$，会对程序效率有很大的提升。

课后，Farmer John 布置了一道题，要求在 $1$ 秒内算出 $f(x)=\sum\limits_{i=1}^x3^{\omega(i)}$。Bessie 用 $20$ 分钟打了一个 $Θ(n\log_2 n\sqrt n)$ 代码，一交直接 TLE。于是，Bessie 来向你求助。

题目描述

她想要求出对于 $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$。

输入格式

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

输出格式

共 $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

提示

【数据规模与约定】 |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}$|

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