#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long f = 1, x = 0;
  char ch;
  do {
    ch = getchar();
    if (ch == '-') f = -1;
  } while (ch < '0' || ch > '9');
  do {
    x = x * 10 + ch - '0';
    ch = getchar();
  } while (ch >= '0' && ch <= '9');
  return f * x;
}
vector<int> v[100005];
map<int, int> ma;
int n, m, l, r, a[100005], b[100005], ttt, le[21], st[100005][21], lga;
int lg2(int t) { return int(log(double(t)) / log(2.0)); }
int gcd(int a, int b) {
  if (b) return gcd(b, a % b);
  return a;
}
void init() {
  le[0] = 1;
  for (register int i = 1; i <= 20; ++i) le[i] = le[i - 1] * 2;
  for (register int i = 1; i <= n; ++i) st[i][0] = a[i];
  for (int j = 1; j < 20; ++j)
    for (int i = 1; i <= n; ++i)
      if (i + le[j] - 1 <= n)
        st[i][j] = gcd(st[i][j - 1], st[i + le[j - 1]][j - 1]);
  return;
}
int que(int l, int r) {
  int tt = lg2(r - l + 1);
  return gcd(st[l][tt], st[r - le[tt] + 1][tt]);
}
int main() {
  n = read();
  ttt = 1;
  for (register int i = 1; i <= n; ++i) {
    a[i] = read();
    b[i] = a[i];
  }
  sort(b + 1, b + n + 1);
  b[0] = 0;
  for (register int i = 1; i <= n; ++i)
    if (b[i] != b[i - 1]) {
      ma[b[i]] = ttt;
      ++ttt;
    }
  for (register int i = 1; i <= n; ++i) v[ma[a[i]]].push_back(i);
  init();
  m = read();
  for (register int i = 1; i <= m; ++i) {
    l = read();
    r = read();
    int w = que(l, r);
    map<int, int>::iterator it = ma.find(w);
    if (it == ma.end()) {
      cout << r - l + 1 << endl;
      continue;
    }
    int qwq = upper_bound(v[ma[w]].begin(), v[ma[w]].end(), r) -
              lower_bound(v[ma[w]].begin(), v[ma[w]].end(), l);
    cout << (r - l + 1) - qwq << endl;
  }
  return 0;
}
