#include <bits/stdc++.h>
using namespace std;
int pos[100010], fpb[262150];
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void build(int id, int l, int r) {
  int m = (l + r) / 2;
  if (l == r)
    pos[l] = id;
  else {
    build((2 * id) + 1, l, m);
    build((2 * id) + 2, m + 1, r);
  }
}
void update(int ind) {
  fpb[ind] = gcd(fpb[(2 * ind) + 1], fpb[(2 * ind) + 2]);
  if (ind > 0) update((ind - 1) / 2);
}
int query(int indeks, int kiri, int kanan, int ql, int qr) {
  int tengah = (kiri + kanan) / 2;
  if ((kanan < ql) || (kiri > qr)) return 0;
  if ((ql <= kiri) && (kanan <= qr)) return fpb[indeks];
  return gcd(query((2 * indeks) + 1, kiri, tengah, ql, qr),
             query((2 * indeks) + 2, tengah + 1, kanan, ql, qr));
}
int main() {
  int n, s, cnt = 0, temp, t, x, y, bpf, left, right, mid, batasl, batasr;
  vector<int> posisi[100010];
  map<int, int> peta;
  scanf("%d", &n);
  build(0, 1, n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &s);
    if (peta.count(s) < 1) peta[s] = cnt++;
    temp = peta[s];
    posisi[temp].push_back(i);
    temp = pos[i];
    fpb[temp] = s;
    update((temp - 1) / 2);
  }
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &x, &y);
    bpf = query(0, 1, n, x, y);
    if (peta.count(bpf) < 1) {
      printf("%d\n", y - x + 1);
      continue;
    }
    temp = peta[bpf];
    batasl = -1;
    batasr = -1;
    left = 0;
    right = posisi[temp].size() - 1;
    while (left <= right) {
      mid = (left + right) / 2;
      if (posisi[temp][mid] < x)
        left = mid + 1;
      else {
        batasl = mid;
        right = mid - 1;
      }
    }
    left = 0;
    right = posisi[temp].size() - 1;
    while (left <= right) {
      mid = (left + right) / 2;
      if (posisi[temp][mid] > y)
        right = mid - 1;
      else {
        batasr = mid;
        left = mid + 1;
      }
    }
    if ((batasl == -1) || (batasr == -1)) {
      printf("%d\n", y - x + 1);
      continue;
    }
    temp = batasr - batasl + 1;
    printf("%d\n", y - x - temp + 1);
  }
  return 0;
}
