#include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn = 1e5 + ;

 int n;

 int a[maxn];

 int d[maxn][];

 map<int,ll> ans;

 int gcd(int a, int b)

 {

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

 }

 void init()

 {

     for(int i=;i<n;i++)  d[i][]=a[i];

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

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

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

 }

 int query(int L, int R)

 {

     int k = ;

     while((<<(k+)) <= R-L+)  k++;

     return gcd(d[L][k],d[R-(<<k)+][k]);

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     int kase = ;

     scanf("%d",&T);

     while(T--)

     {

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

         scanf("%d",&n);

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

         ans.clear();

         init();

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

         {

             int j=i, g=a[i];

             while(j<n)

             {

                 int l=j,r=n-;

                 while(l<r)

                 {

                     int mid=(l+r)>>;

                     if(query(l,r)==g)  l=mid+;

                     else r=mid-;

                 }

                 ans[g]+=l-j+;

                 j=l+;

                 g=gcd(g,a[j]);

             }

         }

         int q; scanf("%d",&q);

         while(q--)

         {

             int l,r;

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

             int g=query(l-,r-);

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

         }

     }

     return ;

 }