#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
long long gcd(long long a, long long b) { return a == 0 ? b : gcd(b % a, a); }
const int maxn = 100005 * 4;
struct Tree {
  int l, r;
  long long int sum;
};
Tree node[maxn];
long long int a[maxn];
void PushUp(int i) {
  node[i].sum = gcd(node[i << 1].sum, node[(i << 1) | 1].sum);
}
void build(int i, int l, int r) {
  node[i].l = l;
  node[i].r = r;
  if (l == r) {
    node[i].sum = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(i << 1, l, mid);
  build((i << 1) | 1, mid + 1, r);
  PushUp(i);
}
long long int getGcd(int i, int l, int r) {
  if (node[i].l == l && node[i].r == r) return node[i].sum;
  int mid = (node[i].l + node[i].r) / 2;
  if (r <= mid)
    return getGcd(i << 1, l, r);
  else if (l > mid)
    return getGcd((i << 1) | 1, l, r);
  else
    return gcd(getGcd(i << 1, l, mid), getGcd((i << 1) | 1, mid + 1, r));
}
int n;
struct Node {
  int rs, ls, sum;
} tr[3300010];
int rt[100010], cnt;
void Insert(int pre, int &rt, long long int l, long long int r,
            long long int num) {
  rt = ++cnt;
  tr[rt].ls = tr[pre].ls;
  tr[rt].rs = tr[pre].rs;
  tr[rt].sum = tr[pre].sum;
  if (l == r && l == num) {
    tr[rt].sum++;
    return;
  }
  long long int mid = (l + r) >> 1;
  if (mid >= num)
    Insert(tr[pre].ls, tr[rt].ls, l, mid, num);
  else
    Insert(tr[pre].rs, tr[rt].rs, mid + 1, r, num);
}
int Query(int rt, long long int l, long long int r, long long int num) {
  if (l == r && l == num) {
    return tr[rt].sum;
  }
  long long int mid = (l + r) >> 1;
  if (mid >= num)
    return Query(tr[rt].ls, l, mid, num);
  else
    return Query(tr[rt].rs, mid + 1, r, num);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    Insert(rt[i - 1], rt[i], 1, 1000000000, a[i]);
  }
  int Q;
  scanf("%d", &Q);
  for (int i = 1; i <= Q; i++) {
    int ql, qr;
    scanf("%d %d", &ql, &qr);
    long long int ansGcd = getGcd(1, ql, qr);
    long long int haveNum = Query(rt[qr], 1, 1000000000, ansGcd) -
                            Query(rt[ql - 1], 1, 1000000000, ansGcd);
    printf("%d\n", qr - ql + 1 - haveNum);
  }
}
