#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int mxn = 111111;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
struct node {
  int g, gcnt;
  node(int _g = 0, int _cnt = 0) : g(_g), gcnt(_cnt) {}
  node operator+(const node& o) {
    node sum = node(0, 0);
    sum.g = gcd(g, o.g);
    if (sum.g == g) sum.gcnt += gcnt;
    if (sum.g == o.g) sum.gcnt += o.gcnt;
    return sum;
  }
} T[mxn << 2];
int s[mxn], n;
void Build(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    T[id] = node(s[l], 1);
    return;
  }
  int mid = (l + r) >> 1;
  Build(id * 2, l, mid);
  Build(id * 2 + 1, mid + 1, r);
  T[id] = T[id * 2] + T[id * 2 + 1];
}
node Get(int u, int v, int id = 1, int l = 1, int r = n) {
  if (v < l || r < u) return node(0, 0);
  if (u <= l && r <= v) return T[id];
  int mid = (l + r) >> 1;
  return Get(u, v, id * 2, l, mid) + Get(u, v, id * 2 + 1, mid + 1, r);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> s[i];
  Build();
  int t;
  cin >> t;
  while (t--) {
    int l, r;
    cin >> l >> r;
    cout << r - l + 1 - Get(l, r).gcnt << "\n";
  }
}
