#include <bits/stdc++.h>
using namespace std;
const int maxn = 100003;
int a[maxn];
vector<pair<int, int> > dp[maxn], t;
int gcd(int x, int y) {
  while (x != 0 && y != 0) {
    if (x > y)
      x %= y;
    else
      y %= x;
  }
  return x + y;
}
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    t.push_back(make_pair(a[i], i));
  }
  sort(t.begin(), t.end());
  dp[1].push_back(make_pair(a[1], 1));
  for (int i = 2; i <= n; i++) {
    int curnod = a[i];
    for (int j = 0; j < dp[i - 1].size(); j++) {
      if (dp[i - 1][j].first % curnod != 0) {
        int nnod = gcd(curnod, dp[i - 1][j].first);
        if (nnod != curnod) {
          if (j)
            dp[i].push_back(make_pair(curnod, dp[i - 1][j - 1].second + 1));
          else
            dp[i].push_back(make_pair(curnod, 1));
        }
        curnod = nnod;
      }
    }
    dp[i].push_back(make_pair(curnod, i));
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    int len = r - l + 1;
    int nod = dp[r][0].first;
    for (int j = 0; j < dp[r].size(); j++) {
      nod = dp[r][j].first;
      if (dp[r][j].second >= len) break;
    }
    cout << len - (lower_bound(t.begin(), t.end(), make_pair(nod, r + 1)) -
                   lower_bound(t.begin(), t.end(), make_pair(nod, l)))
         << "\n";
  }
  cin >> n;
  return 0;
}
