Problem Statement

Define the score of a sequence of positive integers $B = (B_1, B_2, \dots, B_k)$ as $\displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1})$. Given a sequence of positive integers $A = (A_1, A_2, \dots, A_N)$, solve the following problem for $m = 1, 2, \dots, N$.

• There are $2^m - 1$ non-empty subsequences of the sequence $(A_1, A_2, \dots, A_m)$. Find the sum of the scores of all those subsequences, modulo $998244353$. Two subsequences are distinguished if they are taken from different positions in the sequence, even if they coincide as sequences.

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print $N$ lines. The $i$-th line should contain the answer for $m = i$.