Problem Statement

$\mathrm{gcd}(x,y)$ denotes the greatest common divisor of $x$ and $y$.

You are given an integer sequence $A$ of length $N$. Find the number of subsequences $A'=(A'_1,A'_2,\dots , A'_k)$ of $A$, not necessarily contiguous, of length at least $1$, that satisfy the following condition.

• For every integer $i$ satisfying $1 \le i \le k-1$, $\mathrm{gcd}(A'_i,A'_{i+1})>1$

Since the answer can be very large, output the answer modulo $998244353$.

Two subsequences are distinguished if the indices they are taken from differ, even if they are the same as sequences.

Input

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

Output

Output the number of subsequences satisfying the condition, modulo $998244353$.

Sample

4
1 2 3 4

5

1
1

1

10
3 1 7 5 4 10 8 6 2 9

58