#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
struct Info {
  int m, c, g;
};
Info operator+(const Info &A, const Info &B) {
  Info T;
  T.m = min(A.m, B.m);
  T.c = 0;
  if (T.m == A.m) T.c += A.c;
  if (T.m == B.m) T.c += B.c;
  T.g = gcd(A.g, B.g);
  return T;
}
struct Node {
  Node *ch[2];
  int l, r;
  Info I;
} * root;
int seq[111111];
int n, m;
Node *build(int l, int r) {
  if (l == r) {
    return new Node{{NULL, NULL}, l, r, Info{seq[l], 1, seq[l]}};
  }
  auto cur = new Node;
  int mid = (l + r) / 2;
  cur->l = l;
  cur->r = r;
  cur->ch[0] = build(l, mid);
  cur->ch[1] = build(mid + 1, r);
  cur->I = cur->ch[0]->I + cur->ch[1]->I;
  return cur;
}
Info ask(Node *cur, int l, int r) {
  assert(!(cur->r < l || cur->l > r));
  if (l == cur->l && cur->r == r) return cur->I;
  int mid = (cur->l + cur->r) / 2;
  if (l <= mid && mid < r)
    return ask(cur->ch[0], l, mid) + ask(cur->ch[1], mid + 1, r);
  if (r <= mid)
    return ask(cur->ch[0], l, r);
  else
    return ask(cur->ch[1], l, r);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &seq[i]);
  root = build(0, n - 1);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--;
    r--;
    auto I = ask(root, l, r);
    int count;
    if (I.m == I.g)
      count = I.c;
    else
      count = 0;
    printf("%d\n", r - l + 1 - count);
  }
}
