#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100500;
const int INF = 2 * 1e9;
pair<int, int> oper(pair<int, int> a, pair<int, int> b) {
  if (a.first != b.first) return min(a, b);
  return {a.first, a.second + b.second};
}
struct STree {
  vector<pair<int, int> > st;
  int n;
  STree(int n) : st(4 * n + 5, {INF, 0}), n(n) {}
  void init(int k, int s, int e, int *a) {
    if (s + 1 == e) {
      st[k] = {a[s], 1};
      return;
    }
    int m = (s + e) / 2;
    init(2 * k, s, m, a);
    init(2 * k + 1, m, e, a);
    st[k] = oper(st[2 * k], st[2 * k + 1]);
  }
  void upd(int k, int s, int e, int p, pair<int, int> v) {
    if (s + 1 == e) {
      st[k] = v;
      return;
    }
    int m = (s + e) / 2;
    if (p < m)
      upd(2 * k, s, m, p, v);
    else
      upd(2 * k + 1, m, e, p, v);
    st[k] = oper(st[2 * k], st[2 * k + 1]);
  }
  pair<int, int> query(int k, int s, int e, int a, int b) {
    if (s >= b || e <= a) return {INF, 0};
    if (s >= a && e <= b) return st[k];
    int m = (s + e) / 2;
    return oper(query(2 * k, s, m, a, b), query(2 * k + 1, m, e, a, b));
  }
  void init(int *a) { init(1, 0, n, a); }
  void upd(int p, pair<int, int> v) { upd(1, 0, n, p, v); }
  pair<int, int> query(int a, int b) { return query(1, 0, n, a, b); }
};
long long gcd(long long a, long long b) { return (b ? gcd(b, a % b) : a); }
struct GTree {
  vector<int> st;
  int n;
  GTree(int n) : st(4 * n + 5, 0), n(n) {}
  void init(int k, int s, int e, int *a) {
    if (s + 1 == e) {
      st[k] = a[s];
      return;
    }
    int m = (s + e) / 2;
    init(2 * k, s, m, a);
    init(2 * k + 1, m, e, a);
    st[k] = gcd(st[2 * k], st[2 * k + 1]);
  }
  void upd(int k, int s, int e, int p, int v) {
    if (s + 1 == e) {
      st[k] = v;
      return;
    }
    int m = (s + e) / 2;
    if (p < m)
      upd(2 * k, s, m, p, v);
    else
      upd(2 * k + 1, m, e, p, v);
    st[k] = gcd(st[2 * k], st[2 * k + 1]);
  }
  int query(int k, int s, int e, int a, int b) {
    if (s >= b || e <= a) return 0;
    if (s >= a && e <= b) return st[k];
    int m = (s + e) / 2;
    return gcd(query(2 * k, s, m, a, b), query(2 * k + 1, m, e, a, b));
  }
  void init(int *a) { init(1, 0, n, a); }
  void upd(int p, int v) { upd(1, 0, n, p, v); }
  int query(int a, int b) { return query(1, 0, n, a, b); }
};
int n, S[MAXN];
int main() {
  while (scanf("%d", &n) >= 1) {
    STree M(n);
    GTree G(n);
    for (int i = (0); i < (int)(n); i++) scanf("%d", &S[i]);
    M.init(S);
    G.init(S);
    int q;
    scanf("%d", &q);
    for (int _ = (0); _ < (int)(q); _++) {
      int l, r;
      scanf("%d %d", &l, &r);
      l--;
      pair<int, int> t = M.query(l, r);
      int g = G.query(l, r);
      printf("%d\n", r - l - (g % t.first ? 0 : t.second));
    }
  }
  return 0;
}
