#include <bits/stdc++.h>
using namespace std;
int N, M;
int ants[100010];
const int size = 131072;
const int init_value = 0;
int gcd_inner(int a, int b) {
  if (b == 0) return a;
  return gcd_inner(b, a % b);
}
int gcd(int a, int b) {
  if (a == 0 && b == 0) return 0;
  if (b == 0) return a;
  return gcd_inner(a, b);
}
int itree[size * 2 + 1];
int counts[size * 2 + 1];
void init() {
  for (int i = 1; i <= size * 2; i++) {
    itree[i] = init_value;
    counts[i] = 0;
  }
}
void update(int pos, int val) {
  pos |= size;
  itree[pos] = val;
  counts[pos] = 1;
  while (pos >>= 1) {
    itree[pos] = gcd(itree[pos << 1], itree[pos << 1 | 1]);
    counts[pos] = 0;
    if (itree[pos] == itree[pos << 1]) {
      counts[pos] += counts[pos << 1];
    }
    if (itree[pos] == itree[pos << 1 | 1]) {
      counts[pos] += counts[pos << 1 | 1];
    }
  }
}
int getrange(int s, int e) {
  int ret = init_value;
  s |= size;
  e |= size;
  while (s <= e) {
    if (s & 1) ret = gcd(ret, itree[s]);
    if ((e & 1) == 0) ret = gcd(ret, itree[e]);
    s = (s + 1) >> 1;
    e = (e - 1) >> 1;
  }
  return ret;
}
int getcounts(int s, int e, int val) {
  int ret = 0;
  s |= size;
  e |= size;
  while (s <= e) {
    if (s & 1) ret += (itree[s] == val) ? counts[s] : 0;
    if ((e & 1) == 0) ret += (itree[e] == val) ? counts[e] : 0;
    s = (s + 1) >> 1;
    e = (e - 1) >> 1;
  }
  return ret;
}
void process() {
  init();
  cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> ants[i];
    update(i + 1, ants[i]);
  }
  int t = 0;
  cin >> t;
  while (t-- > 0) {
    int L, R;
    cin >> L >> R;
    int gcdp = getrange(L, R);
    cout << (R - L + 1) - getcounts(L, R, gcdp) << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  process();
  return 0;
}
