#include <bits/stdc++.h>
using namespace std;
const int N = 100500;
const int inf = 2000000000;
int n;
vector<pair<int, int> > tmin(2 * N);
vector<int> tgcd(2 * N);
int gcd(int a, int b) {
  if (a < b) swap(a, b);
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
pair<int, int> min(pair<int, int> a, pair<int, int> b) {
  if (a.first < b.first) return a;
  if (b.first < a.first) return b;
  return make_pair(a.first, a.second + b.second);
}
void upd(int pos, int x) {
  pos += n;
  tgcd[pos] = x;
  tmin[pos] = make_pair(x, 1);
  for (pos >>= 1; pos; pos >>= 1) {
    tmin[pos] = min(tmin[pos * 2], tmin[pos * 2 + 1]);
    tgcd[pos] = gcd(tgcd[pos * 2], tgcd[pos * 2 + 1]);
  }
}
pair<int, int> getmin(int l, int r) {
  pair<int, int> ans = make_pair(inf, 0);
  for (l += n, r += n; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
    if (l & 1) ans = min(ans, tmin[l]);
    if (!(r & 1)) ans = min(ans, tmin[r]);
  }
  return ans;
}
int getgcd(int l, int r) {
  int ans = 0;
  for (l += n, r += n; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
    if (l & 1) ans = gcd(ans, tgcd[l]);
    if (!(r & 1)) ans = gcd(ans, tgcd[r]);
  }
  return ans;
}
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    upd(i, a);
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    pair<int, int> p = getmin(l, r);
    int otv = r - l + 1;
    if (getgcd(l, r) % p.first == 0) otv -= p.second;
    cout << otv << "\n";
  }
}
