#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, a[N];
struct node {
  int l, r, v, s;
} t[4 * N];
int gcd(int m, int n) {
  if (n == 0) return m;
  return gcd(n, m % n);
}
void build(int num, int l, int r) {
  t[num].l = l, t[num].r = r;
  if (l == r) {
    t[num].v = a[l], t[num].s = r - l + 1;
    return;
  }
  int mid = (l + r) / 2;
  build(2 * num, l, mid);
  build(2 * num + 1, mid + 1, r);
  if (t[2 * num].v == t[2 * num + 1].v) {
    t[num].v = t[2 * num].v, t[num].s = t[2 * num].s + t[2 * num + 1].s;
    return;
  }
  t[num].v = gcd(t[2 * num].v, t[2 * num + 1].v);
  if (t[num].v == t[2 * num].v)
    t[num].s = t[2 * num].s;
  else if (t[num].v == t[2 * num + 1].v)
    t[num].s = t[2 * num + 1].s;
  else
    t[num].s = 0;
}
node query(int num, int l, int r) {
  node tt, t1, t2;
  if (t[num].l > r || t[num].r < l) {
    tt.v = tt.s = 0;
    return tt;
  }
  if (t[num].l >= l && t[num].r <= r) return t[num];
  t1 = query(2 * num, l, r), t2 = query(2 * num + 1, l, r);
  if (t1.v == t2.v) {
    tt.v = t1.v, tt.s = t1.s + t2.s;
    return tt;
  }
  tt.v = gcd(t1.v, t2.v);
  if (tt.v == t1.v)
    tt.s = t1.s;
  else if (tt.v == t2.v)
    tt.s = t2.s;
  else
    tt.s = 0;
  return tt;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  build(1, 1, n);
  int l, r, k, t;
  scanf("%d", &k);
  while (k--) {
    scanf("%d%d", &l, &r);
    printf("%d\n", r - l + 1 - query(1, l, r).s);
  }
  return 0;
}
