#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << ' ' << H;
  dbg_out(T...);
}
const long long mxn = 1e5;
const long long INF = 2e18;
const int32_t M = 1000000007;
const long double pie = acos(-1);
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
 public:
  segtree() : segtree(0) {}
  explicit segtree(long long n) : segtree(std::vector<S>(n, e())) {}
  explicit segtree(const std::vector<S> &v) : _n((long long)(v.size())) {
    log = segtree::ceil_pow2(_n);
    size = 1 << log;
    d = std::vector<S>(2 * size, e());
    for (long long i = 0; i < _n; i++) d[size + i] = v[i];
    for (long long i = size - 1; i >= 1; i--) {
      update(i);
    }
  }
  void set(long long p, S x) {
    assert(0 <= p && p < _n);
    p += size;
    d[p] = x;
    for (long long i = 1; i <= log; i++) update(p >> i);
  }
  S get(long long p) const {
    assert(0 <= p && p < _n);
    return d[p + size];
  }
  S prod(long long l, long long r) const {
    assert(0 <= l && l <= r && r <= _n);
    S sml = e(), smr = e();
    l += size;
    r += size;
    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }
    return op(sml, smr);
  }
  S all_prod() const { return d[1]; }
  template <bool (*f)(S)>
  long long max_right(long long l) const {
    return max_right(l, [](S x) { return f(x); });
  }
  template <class F>
  long long max_right(long long l, F f) const {
    assert(0 <= l && l <= _n);
    assert(f(e()));
    if (l == _n) return _n;
    l += size;
    S sm = e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(op(sm, d[l]))) {
        while (l < size) {
          l = (2 * l);
          if (f(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    } while ((l & -l) != l);
    return _n;
  }
  template <bool (*f)(S)>
  long long min_left(long long r) const {
    return min_left(r, [](S x) { return f(x); });
  }
  template <class F>
  long long min_left(long long r, F f) const {
    assert(0 <= r && r <= _n);
    assert(f(e()));
    if (r == 0) return 0;
    r += size;
    S sm = e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(op(d[r], sm))) {
        while (r < size) {
          r = (2 * r + 1);
          if (f(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

 private:
  long long _n, size, log;
  std::vector<S> d;
  void update(long long k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
  long long ceil_pow2(long long n) {
    long long x = 0;
    while ((1U << x) < (unsigned long long)(n)) x++;
    return x;
  }
};
pair<long long, long long> binary_operation_min(pair<long long, long long> a,
                                                pair<long long, long long> b) {
  if (a.first < b.first)
    return a;
  else if (a.first > b.first)
    return b;
  else
    return {a.first, a.second + b.second};
}
pair<long long, long long> identity_element_min() { return {INF, 0}; }
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long binary_operation_gcd(long long a, long long b) { return gcd(a, b); }
long long identity_element_gcd() { return 0; }
void solve_LOG() {
  long long n;
  cin >> n;
  segtree<pair<long long, long long>, binary_operation_min,
          identity_element_min>
      tree1(n);
  segtree<long long, binary_operation_gcd, identity_element_gcd> tree2(n);
  for (long long i = 0; i <= n - 1; i++) {
    long long x;
    cin >> x;
    tree1.set(i, {x, 1});
    tree2.set(i, x);
  }
  long long q;
  cin >> q;
  while (q--) {
    long long l, r;
    cin >> l >> r;
    --l;
    --r;
    auto p = tree1.prod(l, r + 1);
    long long g = tree2.prod(l, r + 1);
    long long cnt = r - l + 1;
    if (g == p.first) cnt -= p.second;
    cout << cnt;
    cout << "\n";
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long _t = 1;
  for (long long i = 1; i <= _t; i++) {
    solve_LOG();
  }
  return 0;
}
