#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 20005;

int n, m, Q, a[N], phi[N], num[N];
vector<int> f[N];
LL ans[N], sum;

struct Query {
	int l, r, b, id;
	bool operator<(const Query& rhs) const {
		if(b != rhs.b) return b < rhs.b;
		return r < rhs.r;
	}
} q[N];

void init() {
	for(int i = 0; i < N; ++i) phi[i] = i;
	for(int i = 2; i < N; ++i) if(phi[i] == i) {
		for(int j = i; j < N; j += i) {
			phi[j] = phi[j]/i*(i-1);
		}
	}
	for(int i = 1; i < N; ++i) {
		for(int j = 1; j*j <= i; ++j) if(i % j == 0) {
			f[i].push_back(j);
			if(i/j != j) f[i].push_back(i/j);
		}
	}
}

void insert(int x) {
	for(size_t i = 0; i < f[x].size(); ++i) {
		int d = f[x][i];
		sum += (LL)phi[d]*num[d]++;
	}
}

void remove(int x) {
	for(size_t i = 0; i < f[x].size(); ++i) {
		int d = f[x][i];
		sum -= (LL)phi[d]*--num[d];
	}
}

int main(){
	init();
	int T; scanf("%d", &T);
	for(int cas = 1; cas <= T; ++cas) {
		scanf("%d", &n);
		m = sqrt(1.0*n);
		memset(num, 0, sizeof(int)*(n+1));
		for(int i = 0; i < n; ++i) scanf("%d", a+i);
		scanf("%d", &Q);
		for(int l, r, i = 0; i < Q; ++i) {
			scanf("%d%d", &l, &r); --l, --r;
			q[i].l = l, q[i].r = r;
			q[i].b = l / m;
			q[i].id = i;
		}
		sort(q, q+Q);
		sum = 0;
		int pl = q[0].l, pr = q[0].r;
		for(int i = pl; i <= pr; ++i) insert(a[i]);
		ans[q[0].id] = sum;
		for(int i = 1; i < Q; ++i) {
			int l = q[i].l, r = q[i].r;
			if(pl < l) {
				for(int j = pl; j < l; ++j) remove(a[j]);
			} else {
				for(int j = l; j < pl; ++j) insert(a[j]);
			}
			if(pr < r) {
				for(int j = r; j > pr; --j) insert(a[j]);
			} else {
				for(int j = pr; j > r; --j) remove(a[j]);
			}
			ans[q[i].id] = sum;
			pl = l, pr = r;
		}
		printf("Case #%d:\n", cas);
		for(int i = 0; i < Q; ++i) {
			printf("%lld\n", ans[i]);
		}
	}
}