#include <bits/stdc++.h>
using namespace std;
const int MaxN = (1 << 17), INF = 0x3f3f3f3f;
pair<pair<int, int>, int> Tree[2 * MaxN];
int v[MaxN];
int n, RgLim, q;
inline void LimInit() {
  RgLim = log2(n);
  RgLim += ((1 << RgLim) < n);
  RgLim = (1 << RgLim);
}
inline int Gcd(int a, int b) {
  int r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline void BuildNode(pair<pair<int, int>, int> &node,
                      pair<pair<int, int>, int> &Lf,
                      pair<pair<int, int>, int> &Rg) {
  if (Lf.first.first < Rg.first.first) {
    node.first.first = Lf.first.first;
    node.first.second = Lf.first.second;
  } else if (Rg.first.first < Lf.first.first) {
    node.first.first = Rg.first.first;
    node.first.second = Rg.first.second;
  } else {
    node.first.first = Lf.first.first;
    node.first.second = Lf.first.second + Rg.first.second;
  }
  node.second = Gcd(Lf.second, Rg.second);
}
void BuildTree(int l = 1, int r = RgLim, int node = 1) {
  if (l == r) {
    Tree[node] = make_pair(make_pair(v[l], 1), v[l]);
    return;
  }
  int med = (l + r) / 2;
  int Lf = node * 2;
  int Rg = node * 2 + 1;
  BuildTree(l, med, Lf);
  BuildTree(med + 1, r, Rg);
  BuildNode(Tree[node], Tree[Lf], Tree[Rg]);
}
void Query(pair<pair<int, int>, int> &Ans, int Lsr, int Rsr, int l = 1,
           int r = RgLim, int node = 1) {
  if (Lsr <= l and Rsr >= r) {
    Ans = Tree[node];
    return;
  }
  int med = (l + r) / 2;
  int Lf = 2 * node;
  int Rg = 2 * node + 1;
  pair<pair<int, int>, int> Ans1 = make_pair(make_pair(INF, 0), 0);
  pair<pair<int, int>, int> Ans2 = make_pair(make_pair(INF, 0), 0);
  if (Lsr <= med) {
    Query(Ans1, Lsr, Rsr, l, med, Lf);
  }
  if (Rsr > med) {
    Query(Ans2, Lsr, Rsr, med + 1, r, Rg);
  }
  BuildNode(Ans, Ans1, Ans2);
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> v[i];
  }
  LimInit();
  BuildTree();
  cin >> q;
  for (int i = 1; i <= q; ++i) {
    pair<pair<int, int>, int> QAns = make_pair(make_pair(INF, 0), 0);
    int l, r;
    cin >> l >> r;
    Query(QAns, l, r);
    if (QAns.second != QAns.first.first) {
      QAns.first.second = 0;
    }
    cout << r - l + 1 - QAns.first.second << '\n';
  }
  return 0;
}
