You are exploring the stunning region of Natlan! This region consists of $$$n$$$ cities, and each city is rated with an attractiveness $$$a_i$$$. A directed edge exists from City $$$i$$$ to City $$$j$$$ if and only if $$$i \lt j$$$ and $$$\gcd(a_i,a_j)\neq 1$$$, where $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Starting from City $$$1$$$, your task is to determine the total number of distinct paths you can take to reach City $$$n$$$, modulo $$$998\,244\,353$$$. Two paths are different if and only if the set of cities visited is different.

Input

The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of cities.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \leq a_i \leq 10^6$$$) — the attractiveness of each city.

Output

Output the total number of distinct paths you can take to reach City $$$n$$$, modulo $$$998\,244\,353$$$.

Note

In the first example, the five paths are the following:

City $$$1\rightarrow$$$ City $$$5$$$
City $$$1\rightarrow$$$ City $$$2\rightarrow$$$ City $$$5$$$
City $$$1\rightarrow$$$ City $$$2\rightarrow$$$ City $$$3\rightarrow$$$ City $$$5$$$
City $$$1\rightarrow$$$ City $$$2\rightarrow$$$ City $$$4\rightarrow$$$ City $$$5$$$
City $$$1\rightarrow$$$ City $$$4\rightarrow$$$ City $$$5$$$

In the second example, the two paths are the following:

City $$$1\rightarrow$$$ City $$$3\rightarrow$$$ City $$$5$$$
City $$$1\rightarrow$$$ City $$$2\rightarrow$$$ City $$$3\rightarrow$$$ City $$$5$$$

Natlan Exploring

Examples