D. The LCM Weave
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let there be a function defined as: $$$f(X, Y) = \left\lfloor \frac{\mathrm{lcm}(X, Y)}{X \cdot Y} \right\rfloor $$$

You are given an array $$$A$$$ of $$$N$$$ integers. Your task is to compute the sum of $$$f(X, Y)$$$ over all possible unordered pairs$$$(X, Y)$$$ formed from the array.

$$$\dagger$$$ An unordered pairs refers to a selection of two distinct indices $$$i, j$$$ such that $$$i \ne j$$$, and the corresponding elements are $$$X = A[i],\ Y = A[j]$$$. Note that the values $$$X, Y$$$ may be equal, but the indices must be different. Each unique set of indices should be considered only once, regardless of the order.

Input

The first line contains a single integer $$$N (2 \leq N \leq 2⋅10^5)$$$, the number of elements.

The second line contains $$$N$$$ space-separated integers $$$A_1, A_2, \ldots, A_N$$$ $$$(1 \leq A_i \leq 10^6)$$$.

Output

Print the total sum of $$$f(X,Y)$$$ over all valid unordered triples.

Example
Input
6
15 4 8 3 2 6
Output
6