#include <bits/stdc++.h>
using namespace std;
const int maxn = 4 * 100 * 1000 + 100;
const int oo = 10000 * 1000 * 100 + 1000;
int a[maxn], g[maxn], mn[maxn], t[maxn];
struct st {
  int x, y, z;
  st() {}
  st(int a, int b, int c) : x(a), y(b), z(c) {}
};
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  if (a == b || b == 0) return a;
  return gcd(a % b, b);
}
void build(int v, int s, int e) {
  if (e - s == 1) {
    g[v] = a[s];
    mn[v] = a[s];
    t[v] = 1;
    return;
  }
  int mid = (s + e) / 2;
  build(v * 2, s, mid);
  build(v * 2 + 1, mid, e);
  mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
  g[v] = gcd(g[v * 2], g[v * 2 + 1]);
  if (mn[v] == mn[2 * v]) t[v] += t[2 * v];
  if (mn[v] == mn[2 * v + 1]) t[v] += t[v * 2 + 1];
}
st get(int v, int s, int e, int qs, int qe) {
  if (qe <= s || qs >= e) return st(0, 0, oo);
  if (qs <= s && qe >= e) return st(g[v], t[v], mn[v]);
  int mid = (s + e) / 2;
  st ans(0, 0, oo);
  st a = get(v * 2, s, mid, qs, qe);
  st b = get(v * 2 + 1, mid, e, qs, qe);
  ans.x = gcd(a.x, b.x);
  ans.z = min(a.z, b.z);
  if (a.z == ans.z) ans.y += a.y;
  if (ans.z == b.z) ans.y += b.y;
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  build(1, 0, n);
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    st gt = get(1, 0, n, l, r);
    if (gt.x == gt.z)
      cout << r - l - gt.y << endl;
    else
      cout << r - l << endl;
  }
  return 0;
}
