問題文

魔導師であるあなたは，$1$ から $N$ までの番号が付いた $N$ 種類の「魔導石」を持っています．番号 $i$ の石の魔力強度は $c_i$ です．

あなたは，これらの石の中からいくつか（1個以上）を選んで魔法陣に配置します．選んだ石の集合を $S$ としたとき，その組み合わせの「合計魔力」と「共鳴周波数」は以下のように定義されます．

• 合計魔力: 選んだ石の魔力強度の積．すなわち $\prod_{i \in S} c_i$．
• 共鳴周波数: 選んだ石の番号の最大公約数（GCD）．すなわち $\gcd(\{i \mid i \in S\})$．

すべての $k \in \{1, 2, \dots, N\}$ について，共鳴周波数がちょうど $k$ となるような，あらゆる石の組み合わせの合計魔力の総和を求めてください．

答えは非常に大きくなる可能性があるため，$998244353$ で割った余りを出力してください．

制約

• $1 \le N \le 2 \times 10^5$
• $0 \le c_i < 998244353$

入力

入力は以下の形式で標準入力から与えられる．

出力

$N$ 行出力してください．$k$ 行目には，共鳴周波数が $k$ となる組み合わせの合計魔力の総和を $998244353$ で割った余りを出力してください．

サンプル

4
2 5 3 4

327
25
3
4

1. k=4 のとき: 石 $\{4\}$ だけが選ばれた場合．合計魔力 = 4
2. k=3 のとき: 石 $\{3\}$ だけが選ばれた場合．合計魔力 = 3
3. k=2 のとき: $\gcd$ が $2$ になる組み合わせは $\{2\}$ と $\{2, 4\}$．
   • $\{2\}$ の魔力: $5$
   • $\{2, 4\}$ の魔力: $5 \times 4 = 20$
   • 合計: $5 + 20 =$ 25
4. k=1 のとき: $\gcd$ が $1$ になる全組み合わせ（$\{1\}, \{1,2\}, \{1,3\}, \{2,3\}, \dots$）の合計魔力の和．
   • 計算結果: 327