Problem Description

Given a sequence of $n$ integers $a_i$.

Let $\text{mul}(l, r) = \prod_{i = l}^{r} a_i$ and $\text{fac}(l, r)$ be the number of distinct prime factors of $\text{mul}(l, r)$.

Please calculate $\sum_{i = 1}^{n}\sum_{j = i}^{n}\text{fac}(i, j)$

Input Format

The first line contains one integer $n$ ($1 \le n \le 10^6$) $\text{---}$ the length of the sequence.

The second line contains $n$ integers $a_i$ ($1 \le i \le n, 1 \le a_i \le 10^6$) $\text{---}$ the sequence.

Output Format

Print the answer to the equation.

10
99 62 10 47 53 9 83 33 15 24

248

10
6 7 5 5 4 9 9 1 8 12

134