#include <bits/stdc++.h>
using namespace std;
struct node {
  int gcd;
  int mn;
  int cnt;
};
const int N = 1e5 + 5;
const int inf = 1e9 + 5;
node st[N << 2];
node z = {0, inf, 0};
int ants[N];
int n, q;
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
node unite(node a, node b) {
  node tmp;
  tmp.gcd = gcd(a.gcd, b.gcd);
  tmp.mn = min(a.mn, b.mn);
  if (a.mn < b.mn) {
    tmp.cnt = a.cnt;
  } else if (b.mn < a.mn) {
    tmp.cnt = b.cnt;
  } else {
    tmp.cnt = a.cnt + b.cnt;
  }
  return tmp;
}
void build(int x, int l, int r) {
  if (l == r) {
    st[x] = {ants[l], ants[l], 1};
    return;
  }
  int mid = (l + r) / 2;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  st[x] = unite(st[x << 1], st[x << 1 | 1]);
}
node query(int x, int l, int r, int ll, int rr) {
  if (r < ll || rr < l || r < l) return z;
  if (ll <= l && r <= rr) return st[x];
  int mid = (l + r) / 2;
  return unite(query(x << 1, l, mid, ll, rr),
               query(x << 1 | 1, mid + 1, r, ll, rr));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> ants[i];
  }
  build(1, 1, n);
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    node ans = query(1, 1, n, l, r);
    cout << r - l + 1 - (ans.gcd == ans.mn ? ans.cnt : 0) << '\n';
  }
  return 0;
}
