#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp> 
#include<ext/pb_ds/tree_policy.hpp> 
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define endl '\n'
#define ll long long int
#define md 1000000007
#define MP make_pair
#define pb push_back
#define ppb pop_back
 
 
const ll INF=1e9+15;
const ll NAX= 1e5+5; // change it acc tothe contraints
 

vector<ll> arr(NAX);


struct node{
    int num=0;
    int cnt=1;
  /*  node(){
        num=0;
        cnt=0;
        _gcd=0;
    }
    node (int val){
        num=val;
    }

    void merge(node &root, node &left, node& right){
        _gcd=gcd();
    }
    */
};

node null_n;
//node tree[4*NAX];
vector<node> tree;

int gcd(int a,int b)
{
    {int t;while(b){a=a%b;t=a;a=b;b=t;}return a;}
}

void merge(node &root,  node &left,  node &right){
    int gcd_num=gcd(left.num, right.num);
    root.num=gcd_num;
   // int cnt_now=0;
    //debug(root.cnt, root.num, gcd_num);
    if(left.num==root.num and left.num!=0){
        root.cnt+=left.cnt;
       // cnt_now+=1;
        /*
         * root.cnt+=cnt_now;
         * */
    }
    else if(right.num==root.num and right.num!=0){
        root.cnt+=right.cnt;
       //cnt_now+=1;
       // root.cnt+=cnt_now;
    }
    else{
        root.cnt=0;
    }
    
 debug(root.num,left.num, right.num, root.cnt, left.cnt, right.cnt);
}

void build(ll si, ll ss,ll se){
    if(ss==se){
        tree[si].cnt=1;
        tree[si].num=arr[ss];
        //debug(arr[ss]);
        return;
    }

   
       
    int mid=(ss+se)/2;
    int lc=2*si;
    int rc=2*si+1;
    build(2*si, ss,mid);
    build(2*si+1, mid+1,se);
    merge(tree[si],tree[lc],tree[rc]);     
     

    //tree[si]=__gcd(tree[lc], tree[rc]);
   //debug(tree[si].cnt, tree[si].num, lc, rc);
}

void printTree(int i,int l,int r){
    cout<<"id= "<<i<<" "<<"num: "<<tree[i].num<<" "<<"count: "<<tree[i].cnt<<endl;
        //<<" "<<"clse_need: "<<tree[i].close_need<<endl;
    if(l==r){
        return;
    }
 
    int mid = (l+r)/2 ;
    int left = i*2,right = i*2+1;
    printTree(left,l,mid);
    printTree(right,mid+1,r);
}


node query(ll root,ll  node_low, ll node_high, ll  query_low, ll query_high){
    if(node_low>=query_low and query_high>=node_high){
      return tree[root]; 
    }    

    if(query_low>node_high or node_low>query_high){
        return null_n;
    }
    node ans;
     ll mid=(node_low+node_high)/2;
  node lc=query(2*root, node_low, mid, query_low, query_high);

  node rc=query(2*root+1, mid+1, node_high, query_low, query_high);
    merge(ans, lc, rc);
    debug(lc.num, lc.cnt, rc.num, rc.cnt,ans.num, ans.cnt);
    return ans;
}
/*void update(ll root, ll node_low, ll node_high, ll query_low, ll query_high, ll val){
    if(node_low>=query_low and query_high>=node_high){
        tree[root]=val;
        return;
    }
    if(query_low>node_high or node_low>query_high){
        return ;
    }
    ll mid=(node_low+node_high)/2;
     update(2*root, node_low, mid, query_low, query_high, val);
     update(2*root+1, mid+1, node_high, query_low, query_high, val);
     tree[root]=__gcd(tree[2*root],tree[2*root+1]);
}
 */
void solve()
{
   ll n, q;
   cin>>n;
   for(int i=0; i<n; i++){
       cin>>arr[i];
   }
   /* while(__builtin_popcount(n)!=1){
      arr.pb(0);
      n++;
    }
    */
    tree.resize(4*NAX);
    cin>>q;
    build(1,0,n-1);
    cout<<"BEfore: "<<endl;
    printTree(1,0,n-1);
    while(q--){
        ll l,r;
        cin>>l>>r;
        l--;
        r--;
    //debug(tree[0]);
     //   cout<<2*query(1,0,n-1, l,r).len<<endl;
        ll no_ant=0;
         no_ant=r-l+1;
        ll answer=0;
        ll cnt_now=query(1,0,n-1,l,r).cnt;
        if(cnt_now==no_ant-1)answer+=1;
        cout<<no_ant-answer<<endl;
        debug(no_ant, answer, cnt_now);
    }   
 
 
 
}
int main() {
		
 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
int tc=1;
   // cin>>tc;
    for (int i=0; i<tc; i++){
		solve();
		//cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
 
		}
		
 
 
}