Background

Bessie and the others are sitting in the newly merged barn, studying loop unrolling with Farmer John.

Farmer John says that if the unrolling step size is $8$, it can greatly improve program efficiency.

After class, Farmer John assigned a problem: compute $f(x)=\sum\limits_{i=1}^x3^{\omega(i)}$ within $1$ second. Bessie wrote a $Θ(n\log_2 n\sqrt n)$ program in $20$ minutes, but it got TLE right after submission. So Bessie came to you for help.

Problem Description

She wants to compute, for $k\in\{0,1,\dots,7\}$, the value of $f(n)=\sum_{i=1}\limits^n[\omega(i)\equiv k\pmod 8]3^{\omega(i)}$.

In the formula above, $\omega(i)$ denotes how many distinct prime factors $i$ has. For example, $\omega(12)=\omega(6)=2,\omega(114514)=3$.

Input Format

A single line containing an integer $n$.

Output Format

Output $8$ lines. The $k$-th line (for $k=0,1,2,3,4,5,6,7$) should output the value of $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

Constraints

If you need a loop unrolling generator, please download it from the attachment.

Translated by ChatGPT 5