Sum Of Gcd

Given you a sequence of number a₁, a₂, ..., a_n, which is a permutation of 1...n.
You need to answer some queries, each with the following format:
Give you two numbers L, R, you should calculate sum of gcd(a[i], a[j]) for every L <= i < j <= R.

First line contains a number T(T <= 10),denote the number of test cases.
Then follow T test cases.
For each test cases,the first line contains a number n(1<=n<= 20000).
The second line contains n number a₁,a₂,...,a_n.
The third line contains a number Q(1<=Q<=20000) denoting the number of queries.
Then Q lines follows,each lines contains two integer L,R(1<=L<=R<=n),denote a query.

For each case, first you should print "Case #x:", where x indicates the case number between 1 and T.
Then for each query print the answer in one line.

1
5
3 2 5 4 1
3
1 5
2 4
3 3

Case #1:
11
4
0

2013 Multi-University Training Contest 8