5381：The sum of gcd

You have an array $A$,the length of $A$ is $n$
Let $f(l,r)=\sum_{i=l}^{r}\sum_{j=i}^{r}gcd(a_i,a_{i+1}....a_{j})$

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
First line has one integers $n$
Second line has $n$ integers $A_i$
Third line has one integers $Q$,the number of questions
Next there are Q lines,each line has two integers $l$,$r$
$1\leq T \leq 3$
$1\leq n,Q \leq 10^4$
$1\leq a_i \leq 10^9$
$1\leq l<r \leq n$

For each question,you need to print $f(l,r)$