#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)(1e5) + 123;
const int INF = (int)(1e9);
int n, a[maxn], t[4 * maxn], tt;
pair<int, int> b[maxn];
int gcd(int a, int b) {
  while (a > 0 && b > 0) {
    if (a > b)
      a %= b;
    else
      b %= a;
  }
  return a + b;
}
void build(int v, int tl, int tr) {
  if (tl == tr)
    t[v] = a[tl];
  else {
    int tm = (tl + tr) / 2;
    build(v + v, tl, tm);
    build(v + 1 + v, tm + 1, tr);
    t[v] = gcd(t[v + v], t[v + 1 + v]);
  }
}
int get(int v, int tl, int tr, int l, int r) {
  if (l > tr || r < tl) return 0;
  if (l <= tl && r >= tr) return t[v];
  int tm = (tl + tr) / 2;
  return gcd(get(v + v, tl, tm, l, r), get(v + 1 + v, tm + 1, tr, l, r));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    b[i] = make_pair(a[i], i);
  }
  sort(b + 1, b + 1 + n);
  build(1, 1, n);
  cin >> tt;
  for (int i = 1; i <= tt; ++i) {
    int l, r;
    cin >> l >> r;
    int cur = get(1, 1, n, l, r);
    pair<int, int> now = make_pair(cur, l);
    int to = (lower_bound(b + 1, b + 1 + n, now) - (b + 1));
    now = make_pair(cur, r + 1);
    int from = (lower_bound(b + 1, b + 1 + n, now) - (b + 1));
    cout << (r - l + 1) - (from - to) << "\n";
  }
  return 0;
}
