The sum of gcd

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

Sample Input

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

Sample Output

9
6
16
18
23
10

Author

SXYZ

Source

2015 Multi-University Training Contest 8