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\)
f(1,1) = 1
f(1,2) = 3
f(1,3) = 6
f(2,2) = 1
f(2,3) = 3
f(3,3) = 1
sum = 1 + 3 + 6 + 1 + 3 + 1 = \(15\)