#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
vector<pair<int, int> > tree;
int n;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
  if (a.first == b.first) return {a.first, a.second + b.second};
  if (a.first > b.first) swap(a, b);
  if (a.first == -1) return b;
  if (b.first % a.first == 0)
    return a;
  else
    return {gcd(a.first, b.first), 0};
}
void build(vector<int> &a, int v, int tl, int tr) {
  if (tl == tr) {
    tree[v] = {a[tl], 1};
  } else {
    int tm = (tl + tr) / 2;
    build(a, 2 * v, tl, tm);
    build(a, 2 * v + 1, tm + 1, tr);
    tree[v] = combine(tree[2 * v], tree[2 * v + 1]);
  }
}
pair<int, int> get_gcd(int v, int tl, int tr, int l, int r) {
  if (l > r) return {-1, 0};
  if (tl == l && tr == r) return tree[v];
  int tm = (tl + tr) / 2;
  return combine(get_gcd(2 * v, tl, tm, l, min(tm, r)),
                 get_gcd(2 * v + 1, tm + 1, tr, max(tm + 1, l), r));
}
int solve(int l, int r) {
  pair<int, int> gcd_lr = get_gcd(1, 0, n - 1, l, r);
  return (r - l + 1 - gcd_lr.second);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  tree = vector<pair<int, int> >(4 * n, {0, 0});
  vector<int> a(n, 0);
  for (int i = 0; i < (n); i++) {
    cin >> a[i];
  }
  build(a, 1, 0, n - 1);
  int t;
  cin >> t;
  int l, r;
  for (int i = 0; i < (t); i++) {
    cin >> l >> r;
    cout << solve(l - 1, r - 1) << endl;
  }
  return 0;
}
