#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
struct node {
  long long int num;
  long long int hcf;
  long long int num_count;
};
node seg[4 * 100001];
node make_node(long long int v) {
  node t;
  t.hcf = t.num = v;
  t.num_count = 1;
  if (v == 0) t.num_count--;
  return t;
}
node combine(node l, node r) {
  if (l.hcf == 0) return r;
  if (r.hcf == 0) return l;
  long long int val = gcd(l.hcf, r.hcf);
  node t;
  if (val == l.num && val == r.num) {
    t.hcf = val;
    t.num = val;
    t.num_count = l.num_count + r.num_count;
  } else if (val == l.num) {
    t.hcf = val;
    t.num = val;
    t.num_count = l.num_count;
  } else if (val == r.num) {
    t.hcf = val;
    t.num = val;
    t.num_count = r.num_count;
  } else {
    t.hcf = val;
    t.num = 0;
    t.num_count = 0;
  }
  return t;
}
void build(vector<long long int> &vec, long long int tl, long long int tr,
           long long int v) {
  if (tl == tr) {
    seg[v] = make_node(vec[tl]);
    return;
  }
  long long int tm = (tl + tr) / 2;
  build(vec, tl, tm, 2 * v);
  build(vec, tm + 1, tr, 2 * v + 1);
  seg[v] = combine(seg[2 * v], seg[2 * v + 1]);
}
node query(long long int l, long long int r, long long int tl, long long int tr,
           long long int v) {
  if (l > r) return make_node(0);
  if (tl == l && tr == r) return seg[v];
  long long int tm = (tl + tr) / 2;
  node t = combine(query(l, min(r, tm), tl, tm, 2 * v),
                   query(max(l, tm + 1), r, tm + 1, tr, 2 * v + 1));
  return t;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int n;
  cin >> n;
  vector<long long int> vec(n);
  for (int i = 0; i < (n); ++i) {
    cin >> vec[i];
  }
  build(vec, 0, n - 1, 1);
  long long int m;
  cin >> m;
  long long int x, y;
  node t;
  for (int i = 0; i < (m); ++i) {
    cin >> x >> y;
    t = query(x - 1, y - 1, 0, n - 1, 1);
    cout << y - x + 1 - t.num_count << "\n";
  }
  cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
  return 0;
}
