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(al,al+1,_____,ar) 1. Where sub-array contains elements al,al+1,_____,ar.
INPUT CONSTRAINTS
1≤n≤105
1≤ai≤105
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.
{2},{4},{3},{5},{2,4} are 4 subarrays which has gcd greater than 1.