Problem Description

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})$

Input

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$

Output

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

2
5
1 2 3 4 5
3
1 3
2 3
1 4
4
4 2 6 9
3
1 3
2 4
2 3

9
6
16
18
23
10

Author

SXYZ