#include <bits/stdc++.h>
using namespace std;
const int mxx = 1e5 + 5;
int n;
vector<int> tr;
vector<pair<int, int> > t;
int gcd(int a, int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
pair<int, int> comb(pair<int, int> a, pair<int, int> b) {
  pair<int, int> res;
  if (a.first < b.first)
    res = a;
  else if (a.first > b.first)
    res = b;
  else {
    res = a;
    res.second += b.second;
  }
  return res;
}
void build() {
  for (int i = n - 1; i > 0; --i) tr[i] = gcd(tr[i << 1], tr[i << 1 | 1]);
}
void build_min() {
  for (int i = n - 1; i > 0; --i) t[i] = comb(t[i << 1], t[i << 1 | 1]);
}
int query(int l, int r) {
  --l;
  int res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = gcd(res, tr[l++]);
    if (r & 1) res = gcd(tr[--r], res);
  }
  return res;
}
pair<int, int> query_min(int l, int r) {
  --l;
  pair<int, int> res = {1e9, 0};
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = comb(res, t[l++]);
    if (r & 1) res = comb(t[--r], res);
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  tr.resize(n << 1);
  for (int i = 0; i < n; i++) cin >> tr[i + n];
  build();
  t.resize(n << 1);
  for (int i = 0; i < n; i++) t[i + n] = {tr[i + n], 1};
  build_min();
  int q, l, r, c;
  cin >> q;
  while (q--) {
    cin >> l >> r;
    c = query(l, r);
    pair<int, int> d = query_min(l, r);
    int res = r - l + 1;
    if (d.first == c) res -= d.second;
    cout << res << endl;
  }
}
