#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
long long n, a[N];
long long it[4 * N];
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void init(long long k, long long l, long long r) {
  if (l == r) {
    it[k] = a[l];
    return;
  }
  long long mid = (l + r) >> 1;
  long long lc = (k << 1);
  long long rc = lc + 1;
  init(lc, l, mid);
  init(rc, mid + 1, r);
  it[k] = gcd(it[lc], it[rc]);
}
long long get(long long k, long long l, long long r, long long L, long long R) {
  if (l > R || r < L || l > r) return 0;
  if (L <= l && r <= R) return it[k];
  long long mid = (l + r) >> 1;
  long long lc = (k << 1);
  long long rc = lc + 1;
  return gcd(get(lc, l, mid, L, R), get(rc, mid + 1, r, L, R));
}
map<long long, vector<long long> > mp;
signed main() {
  cin >> n;
  for (long long i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
    mp[a[i]].push_back(i);
  }
  init(1, 1, n);
  long long q;
  cin >> q;
  while (q--) {
    long long l, r;
    scanf("%lld%lld", &l, &r);
    long long k = get(1, 1, n, l, r);
    long long cnt = lower_bound(mp[k].begin(), mp[k].end(), r + 1) -
                    lower_bound(mp[k].begin(), mp[k].end(), l);
    cout << r - l - cnt + 1 << "\n";
  }
}
