#include <bits/stdc++.h>
using namespace std;
const int MAXT = (1 << 18);
int tree[MAXT];
map<int, vector<int> > idxof;
int n, t;
int gcd(int a, int b) {
  int tmp;
  while (b) {
    a %= b;
    tmp = a;
    a = b;
    b = tmp;
  }
  return a;
}
int main() {
  scanf("%d", &n);
  int NN;
  for (NN = 1; NN < n; NN *= 2)
    ;
  --NN;
  memset(tree, -1, sizeof tree);
  int s;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &tree[NN + i]);
    idxof[tree[NN + i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    for (int node = (NN + i) / 2; node; node >>= 1) {
      if (tree[2 * node + 1] > 0) {
        tree[node] = gcd(tree[2 * node], tree[2 * node + 1]);
      } else {
        tree[node] = tree[2 * node];
      }
    }
  }
  scanf("%d", &t);
  int l, r;
  for (int i = 1; i <= t; i++) {
    scanf("%d%d", &l, &r);
    int sl = l, sr = r, g = -1;
    l += NN;
    r += NN;
    while (l <= r) {
      if (l & 1) {
        g = (g == -1) ? tree[l] : gcd(g, tree[l]);
      }
      if (!(r & 1)) {
        g = (g == -1) ? tree[r] : gcd(g, tree[r]);
      }
      l = (l + 1) / 2;
      r = (r - 1) / 2;
    }
    l = sl;
    r = sr;
    if (idxof.find(g) == idxof.end()) {
      printf("%d\n", r - l + 1);
    } else {
      vector<int>& currvec = idxof[g];
      int lidx =
          lower_bound(currvec.begin(), currvec.end(), l) - currvec.begin();
      int ridx =
          upper_bound(currvec.begin(), currvec.end(), r) - currvec.begin();
      printf("%d\n", r - l + 1 - (ridx - lidx));
    }
  }
  return 0;
}
