Given $n$ numbers $a_1, a_2, \dots, a_n$, you need to calculate the value of the following expression:

$$\sum_{S \subseteq \{1, 2, \dots, n\}} \varphi\left(\prod_{i \in S} a_i\right)$$

where $\varphi$ is Euler's totient function, and $\varphi(x)$ denotes the number of integers in $[1, x]$ that are coprime to $x$. For example: $\varphi(6) = 2$, because in $[1, 6]$, $1$ and $5$ are coprime to $6$. $\varphi(1) = 1$, because in $[1, 1]$, $1$ is coprime to $1$.

Additionally, we define $\prod_{i \in \emptyset} a_i = 1$.

Since the answer may be very large, you need to output the result modulo $998244353$.

Input

Read the data from standard input. The first line contains an integer $n$ ($1 \le n \le 2000$), representing the number of integers. The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3000$).

Output

Output to standard output. Output a single integer representing the answer modulo $998244353$.

Examples

Input 1

3
1 2 3

Output 1

12

Note 1

There are eight possible choices for $S$. The values of $\prod_{i \in S} a_i$ for all choices are $1, 1, 2, 2, 3, 3, 6, 6$. We can calculate $\varphi(1) = \varphi(2) = 1$ and $\varphi(3) = \varphi(6) = 2$. Therefore, the answer is $1 \times 4 + 2 \times 4 = 12$.