#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (a == 0LL) return b;
  return gcd(b % a, a);
}
class SegTree {
  int n;
  vector<long long> st;

 public:
  SegTree(int n) {
    this->n = n;
    st.resize(4 * n + 2, 0LL);
  }
  void buildHelper(int l, int r, int pos, long long *arr) {
    if (l == r) {
      st[pos] = arr[l];
      return;
    }
    int mid = (l + r) >> 1, lc = pos << 1, rc = lc ^ 1;
    buildHelper(l, mid, lc, arr);
    buildHelper(mid + 1, r, rc, arr);
    st[pos] = gcd(st[lc], st[rc]);
  }
  void updateHelper(int idx, long long val, int l, int r, int pos) {
    if (l == r) {
      st[pos] = val;
      return;
    }
    int mid = (l + r) >> 1, lc = pos << 1, rc = lc ^ 1;
    if (idx <= mid)
      updateHelper(idx, val, l, mid, lc);
    else
      updateHelper(idx, val, mid + 1, r, rc);
    st[pos] = gcd(st[lc], st[rc]);
  }
  long long queryHelper(int ql, int qr, int l, int r, int pos) {
    if (qr < l || ql > r)
      return 0;
    else if (ql <= l && qr >= r)
      return st[pos];
    int mid = (l + r) >> 1, lc = pos << 1, rc = lc ^ 1;
    return gcd(queryHelper(ql, qr, l, mid, lc),
               queryHelper(ql, qr, mid + 1, r, rc));
  }
  void update(int idx, long long val) { updateHelper(idx, val, 1, n, 1); }
  long long query(int ql, int qr) { return queryHelper(ql, qr, 1, n, 1); }
  void build(long long *arr) { buildHelper(1, n, 1, arr); }
};
struct node {
  long long data;
  node *lef, *rig;
  node(long long data) {
    this->data = data;
    lef = NULL;
    rig = NULL;
  }
  node(long long data, node *lef, node *rig) {
    this->data = data;
    this->lef = lef;
    this->rig = rig;
  }
};
class PersistentSegTree {
  int n;
  vector<node *> versions;

 public:
  PersistentSegTree(int n) { this->n = n; }
  node *combine(node *lef, node *rig) {
    return new node(lef->data + rig->data, lef, rig);
  }
  node *buildArray(int l, int r, long long *arr) {
    if (l == r) return new node(arr[l]);
    int mid = (l + r) >> 1;
    return combine(buildArray(l, mid, arr), buildArray(mid + 1, r, arr));
  }
  node *buildEmpty(int l, int r) {
    if (l == r) return new node(0LL);
    int mid = (l + r) >> 1;
    return combine(buildEmpty(l, mid), buildEmpty(mid + 1, r));
  }
  node *updateHelper(int idx, long long val, int l, int r, node *curr) {
    if (l == r) return new node(val);
    int mid = (l + r) >> 1;
    if (idx <= mid)
      return combine(updateHelper(idx, val, l, mid, curr->lef), curr->rig);
    return combine(curr->lef, updateHelper(idx, val, mid + 1, r, curr->rig));
  }
  void build() { versions.push_back(buildEmpty(1, n)); }
  void update(int idx, long long val) {
    versions.push_back(updateHelper(idx, val, 1, n, versions.back()));
  }
  long long queryHelper(int ql, int qr, int l, int r, node *curr) {
    if (qr < l || ql > r)
      return 0;
    else if (ql <= l && qr >= r)
      return (curr->data);
    int mid = (l + r) >> 1;
    return queryHelper(ql, qr, l, mid, curr->lef) +
           queryHelper(ql, qr, mid + 1, r, curr->rig);
  }
  long long query(int version, int ql, int qr) {
    return queryHelper(ql, qr, 1, n, versions[version]);
  }
};
const int N = 1e5 + 5;
int n;
long long a[N], b[N], cnt[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  vector<long long> v;
  for (int i = 1; i <= n; i++) v.push_back(a[i]);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; i++)
    b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
  SegTree S(n);
  S.build(a);
  PersistentSegTree T(n);
  T.build();
  for (int i = 1; i <= n; i++) {
    cnt[b[i]]++;
    T.update(b[i], cnt[b[i]]);
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    long long g = S.query(l, r),
              id = lower_bound(v.begin(), v.end(), g) - v.begin() + 1;
    if (id == 0 || v[id - 1] != g)
      cout << r - l + 1 << "\n";
    else {
      long long safe = T.query(r, id, id) - T.query(l - 1, id, id);
      cout << r - l + 1 - safe << "\n";
    }
  }
}
