#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<map>

using namespace std;

int a[],n,dp[][];

map<int,long long> mp;

int gcd(int a,int b)

{

    return b?gcd(b,a%b):a;

}

void rmq_init(int len)

{

    for(int i = ;i <= len;i++)

    {

        dp[i][] = a[i];

    }

    for(int j = ;(<<j) <= len;j++)

    {

        for(int i = ;i+(<<j)- <= len;i++)

        {

            dp[i][j] = gcd(dp[i][j-],dp[i+(<<(j-))][j-]);

        }

    }

}

int rmq_query(int l,int r)

{

    int k = (int)(log((double)(r-l+))/log(2.0));

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

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int z = ;z <= T;z++)

    {

        mp.clear();

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

        scanf("%d",&n);

        for(int i = ;i <= n;i++)   scanf("%d",&a[i]);

        rmq_init(n);

        for(int i = ;i <= n;i++)

        {

            int l = i,r = i;

            while(r <= n)

            {

                int ll = r,rr = n;

                int v = rmq_query(l,r);

                while(ll <= rr)

                {

                    int mid = (ll+rr)/;

                    if(rmq_query(l,mid) >= v)  ll = mid+;

                    else    rr = mid-;

                }

                mp[v] += ll-r;

                r = ll;

            }

        }

        int t;

        scanf("%d",&t);

        while(t--)

        {

            int l,r;

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

            int ans = rmq_query(l,r);

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

        }

    }

    return ;

}