#include <bits/stdc++.h>
using namespace std;
struct tree {
  int l, r, v, pos, cnt;
  tree() {}
  tree(int tl, int tr) : l(tl), r(tr), v(2147483647), pos(0), cnt(0) {}
} t[100007 * 4];
void build(int l, int r, int i) {
  t[i] = tree(l, r);
  if (l == r) return;
  int mid = (l + r) / 2;
  build(l, mid, i << 1);
  build(mid + 1, r, (i << 1) + 1);
}
void update(int x, int v, int i) {
  if (t[i].l == t[i].r) {
    t[i].v = v;
    t[i].pos = t[i].l;
    t[i].cnt = 1;
    return;
  }
  int mid = (t[i].l + t[i].r) / 2;
  if (x <= mid)
    update(x, v, i << 1);
  else
    update(x, v, (i << 1) + 1);
  t[i].v = min(t[i + i].v, t[i + i + 1].v);
  if (t[i + i].v < t[i + i + 1].v)
    t[i].pos = t[i + i].pos, t[i].cnt = t[i + i].cnt;
  else if (t[i + i].v > t[i + i + 1].v)
    t[i].pos = t[i + i + 1].pos, t[i].cnt = t[i + i + 1].cnt;
  else
    t[i].pos = t[i + i].pos, t[i].cnt = t[i + i].cnt + t[i + i + 1].cnt;
}
int query(int l, int r, int i, int &pos, int &cnt) {
  if (l <= t[i].l && t[i].r <= r) {
    pos = t[i].pos;
    cnt = t[i].cnt;
    return t[i].v;
  }
  if (l > t[i].r || r < t[i].l) {
    pos = 0;
    cnt = 0;
    return 2147483647;
  }
  int pos1, pos2, cnt1, cnt2;
  int ans1 = query(l, r, i + i, pos1, cnt1),
      ans2 = query(l, r, i + i + 1, pos2, cnt2);
  if (ans1 < ans2) {
    pos = pos1;
    cnt = cnt1;
    return ans1;
  } else if (ans2 < ans1) {
    pos = pos2;
    cnt = cnt2;
    return ans2;
  } else {
    pos = pos1;
    cnt = cnt1 + cnt2;
    return ans1;
  }
}
int main() {
  int q;
  int n, a[100007], left[100007], right[100007];
  cin >> n;
  build(1, n, 1);
  for (int i = 1; i <= n; i++) scanf("%d", a + i), update(i, a[i], 1);
  for (int i = 1; i <= n; i++) {
    for (int j = i - 1;;) {
      if (j > 0 && a[j] % a[i] == 0)
        j = left[j] - 1;
      else {
        left[i] = j + 1;
        break;
      }
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = i + 1;;) {
      if (j <= n && a[j] % a[i] == 0)
        j = right[j] + 1;
      else {
        right[i] = j - 1;
        break;
      }
    }
  }
  for (cin >> q; q--;) {
    int l, r, pos, cnt;
    scanf("%d%d", &l, &r);
    query(l, r, 1, pos, cnt);
    if (left[pos] <= l && right[pos] >= r)
      printf("%d\n", r - l + 1 - cnt);
    else
      printf("%d\n", r - l + 1);
  }
  return 0;
}
