#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 100005;
int g[N << 2], cnt[N << 2];
int a[N], ql, qr;
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
void build(int x, int l, int r) {
  if (l == r) {
    g[x] = a[l];
    cnt[x] = 1;
  } else {
    build((x << 1), l, ((l + r) >> 1)),
        build(((x << 1) | 1), ((l + r) >> 1) + 1, r);
    g[x] = gcd(g[(x << 1)], g[((x << 1) | 1)]);
    if (g[(x << 1)] == g[((x << 1) | 1)]) {
      cnt[x] = cnt[(x << 1)] + cnt[((x << 1) | 1)];
    } else if (g[x] == g[(x << 1)]) {
      cnt[x] = cnt[(x << 1)];
    } else if (g[x] == g[((x << 1) | 1)]) {
      cnt[x] = cnt[((x << 1) | 1)];
    } else
      cnt[x] = 0;
  }
}
pair<int, int> query(int x, int l, int r) {
  if (ql <= l && qr >= r) {
    return make_pair(g[x], cnt[x]);
  } else {
    pair<int, int> tt = make_pair(-1, 0), rr = make_pair(-1, 0);
    if (ql <= ((l + r) >> 1)) tt = query((x << 1), l, ((l + r) >> 1));
    if (qr > ((l + r) >> 1)) rr = query(((x << 1) | 1), ((l + r) >> 1) + 1, r);
    if (qr <= ((l + r) >> 1)) return tt;
    if (ql > ((l + r) >> 1)) return rr;
    if (tt.first == rr.first) {
      return make_pair(tt.first, tt.second + rr.second);
    } else if (tt.first % rr.first == 0) {
      return rr;
    } else if (rr.first % tt.first == 0) {
      return tt;
    } else
      return make_pair(gcd(tt.first, rr.first), 0);
  }
}
int main() {
  int t, x, y, z, ca = 1;
  scanf("%d", &(n));
  for (int i = (int)(1); i <= (int)(n); ++i) scanf("%d", &(a[i]));
  build(1, 1, n);
  scanf("%d", &(m));
  while (m--) {
    scanf("%d%d", &(ql), &(qr));
    printf("%d\n", qr - ql + 1 - query(1, 1, n).second);
  }
  return 0;
}
