GCD Sums

Chef has an array $a_1,\ldots, a_n$ of $n$ elements. He wants you to answer queries of the following type: Compute $f(L, R)$, where $$f(L, R) = \sum_{i = L}^{R} \sum_{j= i}^{R} \gcd(a_i, a_{i+1}, \dots a_j).$$ In other words, we want to compute the sum of the greatest common divisors over all subarrays of some range $[L, R]$. Help Chef answer $q$ queries of the described type. ###Input