#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long gcd(long long a, long long b) { return (b == 0 ? a : gcd(b, a % b)); }
long long tree[N * 4];
pair<long long, long long> rmq[N * 4];
vector<long long> v;
void init(int s, int e, int p) {
  if (s == e) {
    rmq[p].first = v[s];
    rmq[p].second = 1;
    tree[p] = v[s];
    return;
  }
  init(s, (s + e) / 2, p * 2);
  init((s + e) / 2 + 1, e, p * 2 + 1);
  tree[p] = gcd(tree[p * 2], tree[p * 2 + 1]);
  if (rmq[p * 2].first == rmq[p * 2 + 1].first)
    rmq[p].first = rmq[p * 2].first,
    rmq[p].second = rmq[p * 2].second + rmq[p * 2 + 1].second;
  else {
    if (rmq[p * 2].first < rmq[p * 2 + 1].first)
      rmq[p].first = rmq[p * 2].first, rmq[p].second = rmq[p * 2].second;
    else
      rmq[p].first = rmq[p * 2 + 1].first,
      rmq[p].second = rmq[p * 2 + 1].second;
  }
  return;
}
long long query(int s, int e, int p, int from, int to) {
  if (from > e || to < s) return -1;
  if (from <= s && e <= to) return tree[p];
  long long a = query(s, (s + e) / 2, p * 2, from, to);
  long long b = query((s + e) / 2 + 1, e, p * 2 + 1, from, to);
  if (a == -1 || b == -1) return max(a, b);
  return gcd(a, b);
}
pair<long long, long long> query2(int s, int e, int p, int from, int to) {
  if (from > e || to < s) return pair<long long, long long>(1e9 + 9, 0);
  if (from <= s && e <= to) return rmq[p];
  pair<long long, long long> a = query2(s, (s + e) / 2, p * 2, from, to);
  pair<long long, long long> b =
      query2((s + e) / 2 + 1, e, p * 2 + 1, from, to);
  pair<long long, long long> c;
  if (a.first == b.first)
    c.first = a.first, c.second = a.second + b.second;
  else {
    if (a.first < b.first)
      c.first = a.first, c.second = a.second;
    else
      c.first = b.first, c.second = b.second;
  }
  return c;
}
int main() {
  int n;
  cin >> n;
  v.resize(n + 1);
  for (int i = 0; i < n; i++) cin >> v[i];
  init(0, n - 1, 1);
  int t, l, r;
  cin >> t;
  while (t--) {
    cin >> l >> r;
    l--, r--;
    pair<long long, long long> a = query2(0, n - 1, 1, l, r);
    if (query(0, n - 1, 1, l, r) == a.first)
      cout << r - l + 1 - a.second << endl;
    else
      cout << r - l + 1 << endl;
  }
  return 0;
}
