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

提示（第一个示例中的 5 条路径）：

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