U185079 [Proi2021]循环展开

$\texttt{peterwuyihong}$ 在学习循环展开，以便于在将来的 $\texttt{CSP-S}$ 骗更多的分。 他知道有**一个数字，叫做** $8$，就是说，循环展开步长为 $8$，一般会对程序效率有**很高的提升**。 有一天，他从**欧拉计划**上**114514**到一个题，$\sum_{i=1}^n3^{\omega(i)}$，他想要用**计算机**跑一下，结果发现计算机跑的不够快，$O(n\sqrt n\log n)$根本跑不过去，于是他**自然而然地**想到了**循环展开**。 每 $8$ 次做一下，程序会跑地**飞快**，于是 $\texttt{peterwuyihong}$ 就学 $\texttt{myee}$，口胡之，不写了，于是你接下了重担。

他想要请你写一个**程序**，对于 $k=0,1,2,3,4,5,6,7$，求出： $$\sum_{i=1}^n[\omega(i)\equiv k(\bmod 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$ 时原式的答案。

【数据规模】 |subtask|$n\le$|所占分值| |:-:|:-:|:-:| |$1$|$100$|$20$| |$2$|$2\times10^6$|$20$| |$3$|$3\times10^7$|$20$| |$4$|$10^9$|$20$| |$5$|$10^{10}$|$20$| 对于所有数据，满足 $1\le n\le 10^{10}$。 **请注意常数因子优化。** 如果你需要一个循环展开生成器，他会放在附件里，非常好用哒！ 如果你要读入输出__int128，推荐[我的快读](https://www.luogu.com.cn/paste/1hec3w24)。