#include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int N=;

 int a[N],n,m,tmp;

 struct tree{

     int l,r,gcd,sum;

 }tr[N*];

 int gcd(int x,int y){

     if(y==)return x;

     else return gcd(y,x%y);

 }

 void update(int now){

     int GCD=gcd(tr[now*].gcd,tr[now*+].gcd);

     tr[now].gcd=GCD;

     if(tr[now*].gcd==tr[now*+].gcd)tr[now].sum=tr[now*].sum+tr[now*+].sum;

     else if(tr[now*].gcd==GCD)tr[now].sum=tr[now*].sum;

     else if(tr[now*+].gcd==GCD)tr[now].sum=tr[now*+].sum;

     else tr[now].sum=;

 }

 void build(int l,int r,int now){

     tr[now].l=l;tr[now].r=r;

     if(l==r){

         tr[now].gcd=a[l];

         tr[now].sum=;

         return;

     }

     int mid=(l+r)>>;

     build(l,mid,now*);

     build(mid+,r,now*+);

     update(now);

 }

 int getgcd(int l,int r,int now){

     if(tr[now].l==l&&tr[now].r==r){

         return tr[now].gcd;

     }

     int mid=(tr[now].l+tr[now].r)>>;

     if(l>mid)return getgcd(l,r,now*+);

     else if(r<=mid)return getgcd(l,r,now*);

     else {

         return gcd(getgcd(l,mid,now*),getgcd(mid+,r,now*+));

     }

 }

 int check(int l,int r,int now){

     if(tr[now].l==l&&tr[now].r==r){

         if(tr[now].gcd==tmp)return tr[now].sum;

         else return ;

     }

     int mid=(tr[now].l+tr[now].r)>>;

     if(l>mid)return check(l,r,now*+);

     else if(r<=mid)return check(l,r,now*);

     else {

         return check(l,mid,now*)+check(mid+,r,now*+);

     }

 }

 int main(){

     while(~scanf("%d",&n)){

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

             scanf("%d",&a[i]);

         }

         build(,n,);

         scanf("%d",&m);

         for(int i=,l,r;i<=m;i++){

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

             tmp=getgcd(l,r,);

             printf("%d\n",r-l+-check(l,r,));

         }

     }

     return ;

 }