#include <bits/stdc++.h>
using namespace std;
long long a[100005];
long long t[500005];
long long gcd(long long p, long long q) {
  if (p < q) {
    long long temp = p;
    p = q;
    q = temp;
  }
  if (q == 0) return p;
  if (p % q == 0) return q;
  return gcd(q, p % q);
}
void build_tree(long long v, long long l, long long h) {
  if (l == h) {
    t[v] = a[l];
    return;
  }
  long long m = (l + h) / 2;
  build_tree(2 * v, l, m);
  build_tree(2 * v + 1, m + 1, h);
  t[v] = gcd(t[2 * v], t[2 * v + 1]);
}
long long query(long long v, long long l, long long r, long long ll,
                long long rr) {
  if (l > r) return 1;
  if (l == ll && r == rr) return t[v];
  long long m = (l + r) / 2;
  long long p = 0, q = 0;
  if (ll <= m) p = query(2 * v, l, m, ll, min(m, rr));
  if (rr > m) q = query(2 * v + 1, m + 1, r, max(ll, m + 1), rr);
  return gcd(p, q);
}
int main() {
  ios_base::sync_with_stdio(0);
  long long n, q;
  cin >> n;
  vector<pair<long long, long long> > v;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    v.push_back(make_pair(a[i], i));
  }
  sort(v.begin(), v.end());
  build_tree(1, 0, n - 1);
  cin >> q;
  while (q--) {
    long long q1, q2;
    cin >> q1 >> q2;
    q1 -= 1;
    q2 -= 1;
    long long g = query(1, 0, n - 1, q1, q2);
    cout << q2 - q1 + 1 + lower_bound(v.begin(), v.end(), make_pair(g, q1)) -
                upper_bound(v.begin(), v.end(), make_pair(g, q2))
         << "\n";
  }
}
