#include <bits/stdc++.h>
using namespace std;
pair<int, pair<int, int> > build(vector<pair<int, pair<int, int> > > &tree,
                                 vector<int> &v, int L, int R, int i) {
  if (L == R - 1) {
    tree[i] = {L, {v[L], 1}};
  } else {
    pair<int, pair<int, int> > a = build(tree, v, L, (L + R) / 2, 2 * i),
                               b = build(tree, v, (L + R) / 2, R, 2 * i + 1);
    if (a.second.first < b.second.first) {
      tree[i] = a;
    } else if (b.second.first < a.second.first) {
      tree[i] = b;
    } else {
      tree[i] = {a.first, {a.second.first, a.second.second + b.second.second}};
    }
  }
  return tree[i];
}
pair<int, pair<int, int> > findmin(vector<pair<int, pair<int, int> > > &tree,
                                   int x, int y, int L, int R, int i) {
  if (x >= R || y <= L) {
    return {0, {1e9 + 10, 0}};
  }
  if (L >= x && R <= y) {
    return tree[i];
  }
  pair<int, pair<int, int> > a = findmin(tree, x, y, L, (L + R) / 2, 2 * i),
                             b = findmin(tree, x, y, (L + R) / 2, R, 2 * i + 1);
  if (a.second.first < b.second.first) {
    return a;
  } else if (b.second.first < a.second.first) {
    return b;
  } else {
    return {a.first, {a.second.first, a.second.second + b.second.second}};
  }
}
int gcd(int x, int y) { return (y == 0 ? x : gcd(y, x % y)); }
int build(vector<int> &tree, vector<int> &v, int L, int R, int i) {
  if (L == R - 1) {
    tree[i] = v[L];
  } else {
    tree[i] = gcd(build(tree, v, L, (L + R) / 2, 2 * i),
                  build(tree, v, (L + R) / 2, R, 2 * i + 1));
  }
  return tree[i];
}
int findmin(vector<int> &tree, int x, int y, int L, int R, int i) {
  if (x >= R || y <= L) {
    return 0;
  }
  if (x <= L && R <= y) {
    return tree[i];
  }
  return gcd(findmin(tree, x, y, L, (L + R) / 2, 2 * i),
             findmin(tree, x, y, (L + R) / 2, R, 2 * i + 1));
}
int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(0);
  int n, m, i, j = 0, k, x, y;
  cin >> n;
  vector<int> v(n);
  vector<vector<int> > mul;
  map<int, int> nmul;
  for (i = 0; i < n; ++i) {
    cin >> v[i];
  }
  vector<pair<int, pair<int, int> > > tree(4 * (n + 10));
  vector<int> tree2(4 * (n + 10));
  build(tree2, v, 0, n, 1);
  build(tree, v, 0, n, 1);
  cin >> m;
  for (i = 0; i < m; ++i) {
    cin >> j >> k;
    pair<int, pair<int, int> > ans = findmin(tree, j - 1, k, 0, n, 1);
    int nans = ans.second.second, min_ans = ans.second.first,
        z = findmin(tree2, j - 1, k, 0, n, 1);
    if (z != min_ans) {
      nans = 0;
    }
    cout << (k - j + 1 - nans) << endl;
  }
  return 0;
}
