Sum of Powers Weighted by Distinct Prime Factors Modulo 8

Given a positive integer n, for each k in \(\{0,1,\dots,7\}\), compute the value of

\[ f(n) = \sum_{i=1}^{n} \left[\omega(i) \equiv k \pmod{8}\right]3^{\omega(i)}, \]

where \(\omega(i)\) is the number of distinct prime factors of \(i\) (for example, \(\omega(12)=\omega(6)=2\) and \(\omega(114514)=3\)). Note that for \(i=1\), define \(\omega(1)=0\).

Your task is to output eight numbers, where the \(k\)th number (starting from \(k=0\)) is the value of \(f(n)\) for that particular congruence condition.

inputFormat

The input consists of a single integer n (\(1 \le n\le 10^6\) or within a reasonable range) on one line.

outputFormat

Output eight space-separated integers, where the \(k\)th integer (for \(k=0,1,\dots,7\)) represents the sum \[ f(n)=\sum_{i=1}^{n} \left[\omega(i) \equiv k \pmod{8}\right]3^{\omega(i)} \] calculated for that corresponding \(k\).

sample

10

1 21 18 0 0 0 0 0