F. Formal Fring
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
I don't think we're alike at all, Mr. White. You're not a cautious man at all... [Y]ou 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 $$$998244353$$$.

Input

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

Output

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

Example
Input
10
Output
1 1 2 1 1 3 6 1 1 2