Killjee has a very easy problem for you. You need to find number of non-co-prime sub-arrays for a given array a containing n elements.

A sub-array of array a is called non-co-prime if gcd(\(a_l\),\(a_{l+1}\),_____,\(a_r\)) 1. Where sub-array contains elements \(a_l\),\(a_{l+1}\),_____,\(a_r\).

INPUT CONSTRAINTS
\(1 \le n \le 10^5\)

\(1\le a_i \le 10^5\)

INPUT FORMAT
First line of input contains a single integer n, denoting number of elements in array a.

Next line contains n space separated integers, elements of array a.

OUTPUT FORMAT
output a single integer number of non-co-prime sub-arrays.