G. 纳塔探索
每个测试点时间限制：4 秒
内存限制：256 兆字节

你正在探索风景壮丽的纳塔地区！这片区域由 $n$ 个城市组成，每个城市有一个吸引力评分 $a_i$。
从城市 $i$ 到城市 $j$ 存在一条有向边当且仅当 $i < j$ 且 $\gcd(a_i, a_j) \neq 1$，其中 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

从城市 $1$ 出发，你的任务是计算到达城市 $n$ 的不同路径总数，对 $998244353$ 取模。
两条路径不同当且仅当它们经过的城市集合不同。

---

输入
第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——城市的数量。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$2 \le a_i \le 10^6$）——每个城市的吸引力。

---

输出
输出到达城市 $n$ 的不同路径总数，对 $998244353$ 取模。

---

样例

样例 1
输入

5
2 6 3 4 6

输出

5

样例 2
输入

5
4 196 2662 2197 121

输出

2

样例 3
输入

7
3 6 8 9 11 12 20

输出

7

样例 4
输入

2
2 3

输出

0

---

注释
在第一个样例中，五条路径如下：

• 城市 $1 \to$ 城市 $5$
• 城市 $1 \to$ 城市 $2 \to$ 城市 $5$
• 城市 $1 \to$ 城市 $2 \to$ 城市 $3 \to$ 城市 $5$
• 城市 $1 \to$ 城市 $2 \to$ 城市 $4 \to$ 城市 $5$
• 城市 $1 \to$ 城市 $4 \to$ 城市 $5$

在第二个样例中，两条路径如下：

• 城市 $1 \to$ 城市 $3 \to$ 城市 $5$
• 城市 $1 \to$ 城市 $2 \to$ 城市 $3 \to$ 城市 $5$