#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> s;
vector<pair<int, int> > g;
inline int gcd(int a, int b) {
  while (a) {
    int t = a;
    a = b % a;
    b = t;
  }
  return b;
}
inline pair<int, int> combine(const pair<int, int>& t1,
                              const pair<int, int>& t2) {
  pair<int, int> res = make_pair(gcd(t1.first, t2.first), 0);
  if (t1.first == res.first) res.second += t1.second;
  if (t2.first == res.first) res.second += t2.second;
  return res;
}
void build(int v, int l, int r) {
  if (l == r) {
    g[v].first = s[l];
    g[v].second = 1;
    return;
  }
  int m = (l + r) / 2;
  build(2 * v, l, m);
  build(2 * v + 1, m + 1, r);
  g[v] = combine(g[2 * v], g[2 * v + 1]);
}
pair<int, int> query(int v, int tl, int tr, int l, int r) {
  if (tl == l && tr == r) {
    return g[v];
  }
  int tm = (tl + tr) / 2;
  if (r <= tm) {
    return query(2 * v, tl, tm, l, min(r, tm));
  } else if (l > tm) {
    return query(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
  } else {
    pair<int, int> t1 = query(2 * v, tl, tm, l, min(r, tm));
    pair<int, int> t2 = query(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
    return combine(t1, t2);
  }
}
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  s.resize(n);
  g.resize(4 * n);
  for (int i = 0; i < n; ++i) cin >> s[i];
  build(1, 0, n - 1);
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    pair<int, int> res = query(1, 0, n - 1, l, r);
    int ans = r - l + 1 - res.second;
    cout << ans << "\n";
  }
  return 0;
}
