#include <bits/stdc++.h>
using namespace std;
struct node {
  int l, r, val, num;
} tree[100005 * 4];
int n, q, tmp[100005];
int gcd(int x, int y) {
  if (!y) return x;
  return gcd(y, x % y);
}
void build(int l, int r, int Index) {
  tree[Index].l = l;
  tree[Index].r = r;
  if (l == r) {
    tree[Index].val = tmp[l];
    tree[Index].num = 1;
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, Index * 2);
  build(mid + 1, r, Index * 2 + 1);
  tree[Index].val = gcd(tree[Index * 2].val, tree[Index * 2 + 1].val);
  tree[Index].num =
      (tree[Index].val == tree[Index * 2].val ? tree[Index * 2].num : 0) +
      (tree[Index].val == tree[Index * 2 + 1].val ? tree[Index * 2 + 1].num
                                                  : 0);
}
int get_gcd(int l, int r, int Index) {
  if (tree[Index].l >= l && tree[Index].r <= r) return tree[Index].val;
  int mid = (tree[Index].l + tree[Index].r) / 2;
  if (r <= mid)
    return get_gcd(l, r, Index * 2);
  else if (l > mid)
    return get_gcd(l, r, Index * 2 + 1);
  else
    return gcd(get_gcd(l, r, Index * 2), get_gcd(l, r, Index * 2 + 1));
}
int query(int l, int r, int Index, int standard) {
  if (tree[Index].l >= l && tree[Index].r <= r)
    return (tree[Index].val == standard) ? tree[Index].num : 0;
  int mid = (tree[Index].l + tree[Index].r) / 2;
  if (r <= mid)
    return query(l, r, Index * 2, standard);
  else if (l > mid)
    return query(l, r, Index * 2 + 1, standard);
  else
    return query(l, r, Index * 2, standard) +
           query(l, r, Index * 2 + 1, standard);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &tmp[i]);
  build(1, n, 1);
  scanf("%d", &q);
  while (q--) {
    int l, r;
    scanf("%d %d", &l, &r);
    printf("%d\n", r - l + 1 - query(l, r, 1, get_gcd(l, r, 1)));
  }
  return 0;
}
