Sum Of Gcd

Problem Description
Given you a sequence of number a1, a2, ..., an, 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.

Input
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 a1,a2,...,an.
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.

Output
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.

Sample Input
1
5
3 2 5 4 1
3
1 5
2 4
3 3

Sample Output
Case #1:
11
4
0