#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 5;
struct Tr {
  long long gcd;
  long long minx;
  long long cnt;
} a[maxn << 2];
long long p[maxn];
long long mygcd(long long a, long long b) {
  return b == 0 ? a : mygcd(b, a % b);
}
void pushup(long long index) {
  a[index].gcd = mygcd(a[index << 1].gcd, a[index << 1 | 1].gcd);
  if (a[index << 1].minx == a[index << 1 | 1].minx) {
    a[index].minx = a[index << 1].minx;
    a[index].cnt = a[index << 1].cnt + a[index << 1 | 1].cnt;
  } else {
    a[index].minx = min(a[index << 1].minx, a[index << 1 | 1].minx);
    a[index].cnt = a[index << 1].minx < a[index << 1 | 1].minx
                       ? a[index << 1].cnt
                       : a[index << 1 | 1].cnt;
  }
}
void build(long long index, long long left, long long right) {
  if (left == right) {
    a[index].gcd = p[left];
    a[index].minx = p[left];
    a[index].cnt = 1;
    return;
  }
  long long mid = left + right >> 1;
  build(index << 1, left, mid);
  build(index << 1 | 1, mid + 1, right);
  pushup(index);
}
long long querygcd(long long index, long long left, long long right,
                   long long start, long long end) {
  if (left <= start && end <= right) {
    return a[index].gcd;
  }
  if (left > end || right < start) {
    return 0;
  }
  long long mid = start + end >> 1;
  return mygcd(querygcd(index << 1, left, right, start, mid),
               querygcd(index << 1 | 1, left, right, mid + 1, end));
}
pair<long long, long long> querymin(long long index, long long left,
                                    long long right, long long start,
                                    long long end) {
  if (left <= start && end <= right) {
    return {a[index].minx, a[index].cnt};
  }
  if (left > end || right < start) {
    return {0x3f3f3f3f, 0};
  }
  long long mid = start + end >> 1;
  auto p1 = querymin(index << 1, left, right, start, mid);
  auto p2 = querymin(index << 1 | 1, left, right, mid + 1, end);
  if (p1.first == p2.first) {
    return {p1.first, p1.second + p2.second};
  }
  return p1.first < p2.first ? p1 : p2;
}
int main() {
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; ++i) {
    cin >> p[i];
  }
  build(1, 1, n);
  long long m;
  cin >> m;
  for (long long i = 0; i < m; ++i) {
    long long x, y;
    cin >> x >> y;
    long long p = querygcd(1, x, y, 1, n);
    auto p2 = querymin(1, x, y, 1, n);
    if (p == p2.first) {
      printf("%lld\n", y - x + 1 - p2.second);
    } else {
      printf("%lld\n", y - x + 1);
    }
  }
  return 0;
}
