#include <bits/stdc++.h>
const int N = 100010;
const int SN = 500;
const int INF = 0x3f3f3f3f;
long long g[N];
class Discretization {
 public:
  Discretization() { vec_.clear(); }
  void Init() { vec_.clear(); }
  void Add(int x) { vec_.push_back(x); }
  void Build() {
    std::sort(vec_.begin(), vec_.end());
    vec_.erase(std::unique(vec_.begin(), vec_.end()), vec_.end());
  }
  int Id(int x) {
    auto y = std::lower_bound(vec_.begin(), vec_.end(), x);
    if (*y != x) {
      return -1;
    } else {
      return y - vec_.begin() + 1;
    }
  }
  int IdLeq(int x) {
    auto y = std::upper_bound(vec_.begin(), vec_.end(), x);
    if (y == vec_.begin()) {
      return 0;
    } else {
      --y;
      return y - vec_.begin() + 1;
    }
  }
  int IdGeq(int x) {
    auto y = std::lower_bound(vec_.begin(), vec_.end(), x);
    if (y == vec_.end()) {
      return vec_.size() + 1;
    } else {
      return y - vec_.begin() + 1;
    }
  }
  int Size() { return vec_.size(); }
  int Value(int id) { return vec_[id - 1]; }

 private:
  std::vector<int> vec_;
} disc;
class GcdInterval {
 public:
  GcdInterval() {}
  int Gcd(int a, int b) { return !b ? a : Gcd(b, a % b); }
  void Init(int n, int a[]) {
    for (int i = 1; i <= n; ++i) {
      vec[i].clear();
    }
    vec[1].push_back(std::pair<int, int>(1, a[1]));
    for (int i = 2; i <= n; ++i) {
      int gcd_tmp = a[i];
      int l_tmp = i;
      for (size_t j = 0; j < vec[i - 1].size(); ++j) {
        int gcd_nxt = Gcd(vec[i - 1][j].second, gcd_tmp);
        if (gcd_nxt != gcd_tmp) {
          vec[i].push_back(std::pair<int, int>(l_tmp, gcd_tmp));
          gcd_tmp = gcd_nxt;
        }
        l_tmp = vec[i - 1][j].first;
      }
      vec[i].push_back(std::pair<int, int>(l_tmp, gcd_tmp));
    }
  }
  int Cal(int l, int r) {
    for (size_t i = 0; i < vec[r].size(); ++i) {
      if (l >= vec[r][i].first) {
        return vec[r][i].second;
      }
    }
    return -1ll;
  }
  std::vector<std::pair<int, int> > vec[N];

 private:
} gcd_interval;
class BlockMo {
 public:
  BlockMo() {}
  void Init(int n, int a[]) {
    n_ = n;
    for (int i = 1; i <= n; ++i) {
      a_[i] = a[i];
    }
    sz = (int)sqrt(n);
    num = 0;
    for (int i = 1; i <= n;) {
      st[++num] = i;
      end[num] = std::min(n, i + sz - 1);
      while (i <= end[num]) {
        id[i] = num;
        ++i;
      }
    }
  }
  void BatchQuery(int nq, int ql[], int qr[], int ans[]) {
    for (int i = 1; i <= nq; ++i) {
      qid[i] = i;
    }
    std::sort(qid + 1, qid + nq + 1,
              [this, ql, qr](const int& x, const int& y) {
                if (id[ql[x]] == id[ql[y]]) {
                  return qr[x] < qr[y];
                } else {
                  return id[ql[x]] < id[ql[y]];
                }
              });
    memset(cnt, 0, sizeof(cnt));
    int l = 1, r = 0;
    long long ans_tmp = 0ll;
    for (int i = 1; i <= nq; ++i) {
      int cur = qid[i];
      while (l > ql[cur]) {
        --l;
        Increase(ans_tmp, a_[l]);
      }
      while (r < qr[cur]) {
        ++r;
        Increase(ans_tmp, a_[r]);
      }
      while (l < ql[cur]) {
        Decrease(ans_tmp, a_[l]);
        ++l;
      }
      while (r > qr[cur]) {
        Decrease(ans_tmp, a_[r]);
        --r;
      }
      ans[cur] = cnt[g[cur]];
    }
  }

 private:
  void Increase(long long& value, int x) { ++cnt[x]; }
  void Decrease(long long& value, int x) { --cnt[x]; }
  int n_;
  int a_[N];
  int id[N];
  int sz;
  int num;
  int st[SN];
  int end[SN];
  int qid[N];
  int cnt[1000100];
} block_mo;
int t;
int n, m;
int a[N];
int ql[N];
int qr[N];
int ans[N];
int main() {
  disc.Init();
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    disc.Add(a[i]);
  }
  gcd_interval.Init(n, a);
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &ql[i], &qr[i]);
    g[i] = gcd_interval.Cal(ql[i], qr[i]);
    disc.Add(g[i]);
  }
  disc.Build();
  for (int i = 1; i <= n; ++i) {
    a[i] = disc.Id(a[i]);
  }
  for (int i = 1; i <= m; ++i) {
    g[i] = disc.Id(g[i]);
  }
  block_mo.Init(n, a);
  block_mo.BatchQuery(m, ql, qr, ans);
  for (int i = 1; i <= m; ++i) {
    printf("%d\n", qr[i] - ql[i] + 1 - ans[i]);
  }
  return 0;
}
