You are given an array of n integer numbers a1, a2, .. ,an.
Define a function f(l,r) as the number of pairs (i,j) such that l≤i≤j≤r and gcd(ai,aj) != 1.
Output the sum of f(l,r) over all l, r such that 1≤l≤r≤n. If the sum is greater than 1018, please output 1.
Input format
Output format
Constraints
1≤n,ai≤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