#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const long long maxn = (long long)1e6 + 6;
const long double EPS = 1e-9;
const long long INF = (long long)1e18 + 18;
const long long mod = (long long)1e9 + 7;
long long n;
map<long long, vector<long long>> positions;
long long gcd(long long a, long long b) { return (b ? gcd(b, a % b) : a); }
struct SegmentTree {
  long long n;
  vector<long long> a;
  vector<long long> t;
  SegmentTree(long long _n) : n(_n) {
    a.resize(n);
    t.resize(4 * n);
  }
  void build(long long id, long long l, long long r) {
    if (l == r) {
      t[id] = a[l];
      return;
    }
    long long mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    t[id] = gcd(t[id << 1], t[id << 1 | 1]);
  }
  long long get(long long id, long long l, long long r, long long ql,
                long long qr) {
    if (l > qr || r < ql) return 0;
    if (l >= ql && r <= qr) return t[id];
    long long mid = (l + r) >> 1;
    return gcd(get(id << 1, l, mid, ql, qr),
               get(id << 1 | 1, mid + 1, r, ql, qr));
  }
  long long get(long long ql, long long qr) { return get(1, 0, n - 1, ql, qr); }
};
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  SegmentTree segtree(n);
  for (long long i = 0; i < n; i++) {
    cin >> segtree.a[i];
    positions[segtree.a[i]].push_back(i);
  }
  segtree.build(1, 0, n - 1);
  long long queries;
  cin >> queries;
  while (queries--) {
    long long left, right;
    cin >> left >> right;
    left--;
    right--;
    long long g = segtree.get(left, right);
    auto st = lower_bound(positions[g].begin(), positions[g].end(), left);
    auto en = upper_bound(positions[g].begin(), positions[g].end(), right);
    long long times = en - st;
    long long dead = right - left + 1 - times;
    cout << dead << '\n';
  }
  return 0;
}
