You are given an array of n integer numbers \(a_1\), \(a_2\), .. ,\(a_n\).

Define a function f(l,r) as the number of pairs \((i, j)\) such that \(l\le i\le j\le r\) and gcd(\(a_i\),\(a_j\)) != 1.

Output the sum of f(l,r) over all l, r such that \(1\le l\le r\le n\). If the sum is greater than \(10^{18}\), please output 1.

Input format

Output format

Constraints

\(1 \le n,a_i \le 100000\)