Formal Fring

I don't think we're alike at all, Mr. White. You're not a cautious man at all... You have poor judgement. I cannot work with someone with poor judgement.

• Gustavo Fring, Breaking Bad

Gus Fring is a very careful man. He doesn't mess with you. When he asks someone to solve a problem, he gives a completely formal statement. And today he asked YOU.

For a positive integer $n$, define $highest\_bit(n)$ as the largest number $i$, such that $2^i \leq n$. Also define $highest\_bit(0) = -1$.

You are given a positive integer $X$. Find the number of multisets $S$ of positive integers, which satisfy the following conditions:

• All elements of $S$ are nonnegative powers of $2$.
• The sum of elements of $S$ is $X$.
• There is no way to split elements of $S$ into two groups so that $highest\_bit(S_1) = highest\_bit(S_2)$, where $S_1$ is the sum of the elements in the first group, and $S_2$ is the sum of the elements in the second group.

Solve this problem for $X = 1, 2, \dots, n$.

Since the answers can be very large, output them modulo $998 \ 244 \ 353$.

Input data

The only line of the input contains a single integer $n$ ($1 \leq n \leq 10^6$).

Output data

Output $n$ integers: answers to the problem for $X = 1, 2, \dots, n$, modulo $998 \ 244 \ 353$.

Example

stdin

10

stdout

1 1 2 1 1 3 6 1 1 2