#include <bits/stdc++.h>
using namespace std;
const long long int MOD1 = 1e9 + 7;
const long long int MOD2 = 998244353;
long long int mod = MOD2;
long long int po(long long int x, long long int y) {
  long long int res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x);
    x = (x * x);
    y >>= 1;
  }
  return res;
}
long long int gcd(int a, int b) {
  if (a < b) swap(a, b);
  if (b == 0) return a;
  return gcd(a % b, b);
}
const int N = 1 << 17;
vector<int> t(2 * N);
void build(vector<int>& a) {
  for (int i = 1; i < a.size(); i++) {
    t[i + N - 1] = a[i];
  }
  for (int i = N - 1; i > 0; i--) {
    t[i] = gcd(t[i << 1], t[i << 1 | 1]);
  }
}
int query(int l, int r) {
  l += N - 1;
  r += N - 1;
  int res = 0;
  while (l < r) {
    if (l & 1) {
      res = gcd(res, t[l]);
      l++;
    }
    if (!(r & 1)) {
      res = gcd(res, t[r]);
      r--;
    }
    l >>= 1;
    r >>= 1;
  }
  if (l == r) {
    res = gcd(res, t[l]);
  }
  return res;
}
void solve() {
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int ii = 1; ii < n + 1; ii++) {
    cin >> a[ii];
  }
  int t;
  cin >> t;
  build(a);
  map<int, vector<int> > m;
  for (int i = 1; i <= n; i++) {
    m[a[i]].push_back(i);
  }
  for (int ii = 0; ii < t; ii++) {
    int l, r;
    cin >> l >> r;
    int x = query(l, r);
    if (m[x].size() == 0)
      x = 0;
    else {
      x = upper_bound(m[x].begin(), m[x].end(), r) -
          lower_bound(m[x].begin(), m[x].end(), l);
    }
    cout << r - l + 1 - x;
    cout << "\n";
    ;
  }
}
int main() {
  { solve(); }
}
