#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b)        for(int i(a); i <= (b); ++i)

#define LL            long long

const int N    =    100000        +    10;

const int A    =    30        +    1;

map <int, LL> mp;

int a[N];

int T;

int n, m;

int l, r;

int f[N][A];

int gcd(int a, int b){return b? gcd(b, a % b) : a;}

inline int Solve(int l, int r){

    int k = (int)log2((double)(r - l + 1));

    return gcd(f[l][k], f[r - (1 << k) + 1][k]);

}

void Work(){

    rep(i, 1, n) f[i][0] = a[i];

    rep(j, 1, 17) rep(i, 1, n) if ((i + (1 << j) - 1) <= n) f[i][j] =gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

}

void setTable(){

    mp.clear();

    rep(i, 1, n){

        int g = f[i][0], j = i;

        while (j <= n){

            int l = j, r = n;

            while (l < r){

                int mid = (l + r + 1) >> 1;

                if (Solve(l, mid) == g) l = mid; else r = mid - 1;

            }

            mp[g] += l - j + 1;

            j = l + 1;

            g = Solve(i, j);

        }

    }

}

int main(){

    scanf("%d", &T);

    rep(Case, 1, T){

        printf("Case #%d:\n", Case);

        scanf("%d", &n);

        rep(i, 1, n) scanf("%d", a + i);

        Work();

        setTable();

        scanf("%d", &m);

        while (m--){

            scanf("%d%d", &l, &r);

            int g = Solve(l, r);

            printf("%d %lld\n", g, mp[g]);

        }

    }

    return 0;

}