#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
int tree[N << 2];
void pushup(int ind) { tree[ind] = gcd(tree[ind << 1], tree[ind << 1 | 1]); }
int a[N];
void build(int ind, int ll, int rr) {
  if (ll == rr) {
    tree[ind] = a[ll];
    return;
  }
  int mid = (ll + rr) >> 1;
  build(((ind) << 1), ll, mid);
  build(((ind) << 1 | 1), mid + 1, rr);
  pushup(ind);
}
int query(int ind, int ll, int rr, int l, int r) {
  if (ll == l && rr == r) {
    return tree[ind];
  }
  int mid = (ll + rr) >> 1;
  if (r <= mid) {
    return query(((ind) << 1), ll, mid, l, r);
  } else if (l > mid) {
    return query(((ind) << 1 | 1), mid + 1, rr, l, r);
  } else {
    int a = query(((ind) << 1), ll, mid, l, mid);
    int b = query(((ind) << 1 | 1), mid + 1, rr, mid + 1, r);
    return gcd(a, b);
  }
}
pair<int, int> re[N];
int t[N], w[N], cnt;
struct PBT {
  int ls[N * 20], rs[N * 20], c[N * 20], tree[N * 20];
  int idx, mx;
  int build(int l, int r) {
    int rt = idx++;
    c[rt] = 0;
    if (l != r) {
      int mid = (l + r) >> 1;
      ls[rt] = build(l, mid);
      rs[rt] = build(mid + 1, r);
    }
    return rt;
  }
  int update(int rt, int pos, int val) {
    int nrt = idx++, ret = nrt;
    c[nrt] = c[rt] + val;
    int l = 1, r = mx;
    while (l != r) {
      int mid = (l + r) >> 1;
      if (pos <= mid) {
        ls[nrt] = idx++;
        rs[nrt] = rs[rt];
        nrt = ls[nrt];
        rt = ls[rt];
        r = mid;
      } else {
        rs[nrt] = idx++;
        ls[nrt] = ls[rt];
        nrt = rs[nrt];
        rt = rs[rt];
        l = mid + 1;
      }
      c[nrt] = c[rt] + val;
    }
    return ret;
  }
  int query(int lrt, int rrt, int pos) {
    int l = 1, r = mx;
    while (l != r) {
      int mid = (l + r) >> 1;
      if (pos <= mid) {
        lrt = ls[lrt];
        rrt = ls[rrt];
        r = mid;
      } else {
        lrt = rs[lrt];
        rrt = rs[rrt];
        l = mid + 1;
      }
    }
    return c[rrt] - c[lrt];
  }
} pbt;
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  build(1, 1, n);
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &re[i].first, &re[i].second);
    t[++cnt] = query(1, 1, n, re[i].first, re[i].second);
    w[i] = t[cnt];
  }
  sort(t + 1, t + cnt + 1);
  cnt = unique(t + 1, t + cnt + 1) - t - 1;
  map<int, int> idx;
  for (int i = 1; i <= cnt; i++) {
    idx[t[i]] = i;
  }
  pbt.mx = cnt;
  pbt.tree[0] = pbt.build(1, cnt);
  for (int i = 1; i <= n; i++) {
    if (idx.count(a[i])) {
      int x = idx[a[i]];
      pbt.tree[i] = pbt.update(pbt.tree[i - 1], x, 1);
    } else {
      pbt.tree[i] = pbt.tree[i - 1];
    }
  }
  for (int i = 0; i < q; i++) {
    int x = re[i].first, y = re[i].second;
    int ret = pbt.query(pbt.tree[x - 1], pbt.tree[y], idx[w[i]]);
    printf("%d\n", re[i].second - re[i].first + 1 - ret);
  }
  return 0;
}
