問題文

$\mathrm{gcd}(x,y)$ で $x$ と $y$ の最大公約数を表します。

長さ $N$ の整数列 $A$ が与えられます。$A$ の連続するとは限らない、長さ $1$ 以上の部分列 $A'=(A'_1,A'_2,\dots , A'_k)$ であって次の条件を満たすものの個数を求めてください。

• $1 \le i \le k-1$ を満たす全ての整数 $i$ に対して $\mathrm{gcd}(A'_i,A'_{i+1})>1$

なお、答えは非常に大きくなる場合があるので答えを $998244353$ で割った余りを出力してください。

ただし、2 つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

条件を満たす部分列の個数を $998244353$ で割った余りを出力してください。

サンプル

4
1 2 3 4

5

1
1

1

10
3 1 7 5 4 10 8 6 2 9

58