#include <bits/stdc++.h>
using namespace std;
int ant[100100], nant, gcdtr[500100], mintr[500100], num[500100], ntree;
int gcd(int a, int b) {
  int r;
  while (a % b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return b;
}
pair<int, pair<int, int> > findtr(int l, int r, int x, int n) {
  if (r < x * n - ntree || l > (x + 1) * n - 1 - ntree)
    return make_pair(-1, make_pair(-1, -1));
  if (l <= x * n - ntree && r >= (x + 1) * n - 1 - ntree)
    return make_pair(gcdtr[x], make_pair(mintr[x], num[x]));
  pair<int, pair<int, int> > lchild, rchild;
  lchild = findtr(l, r, x * 2, n / 2);
  rchild = findtr(l, r, x * 2 + 1, n / 2);
  if (lchild.first == -1) return rchild;
  if (rchild.first == -1) return lchild;
  lchild.first = gcd(lchild.first, rchild.first);
  if (lchild.second.first > rchild.second.first) {
    lchild.second.first = rchild.second.first;
    lchild.second.second = rchild.second.second;
  } else if (lchild.second.first == rchild.second.first)
    lchild.second.second += rchild.second.second;
  return lchild;
}
int main() {
  pair<int, pair<int, int> > cntn;
  int gcdant, minant, surv, nq, l, r, mia, cnt, q, i, j, k;
  scanf("%d", &nant);
  for (i = 0; i < nant; i++) scanf("%d", &ant[i]);
  ntree = 1;
  while (ntree < nant) ntree *= 2;
  for (i = 0; i < ntree; i++) {
    if (i >= nant) {
      gcdtr[i + ntree] = 1;
      mintr[i + ntree] = 1000000001;
      num[i + ntree] = 0;
    } else {
      gcdtr[i + ntree] = ant[i];
      mintr[i + ntree] = ant[i];
      num[i + ntree] = 1;
    }
  }
  for (i = ntree - 1; i > 0; i--) {
    gcdtr[i] = gcd(gcdtr[i * 2], gcdtr[i * 2 + 1]);
    if (mintr[i * 2] < mintr[i * 2 + 1] && mintr[i * 2] != 1000000001) {
      mintr[i] = mintr[i * 2];
      num[i] = num[i * 2];
    } else if (mintr[i * 2] > mintr[i * 2 + 1] && mintr[i * 2] != 1000000001) {
      mintr[i] = mintr[i * 2 + 1];
      num[i] = num[i * 2 + 1];
    } else if (mintr[i * 2] == mintr[i * 2 + 1] && mintr[i * 2] != 1000000001) {
      mintr[i] = mintr[i * 2];
      num[i] = num[i * 2] + num[i * 2 + 1];
    } else {
      mintr[i] = 1000000001;
      num[i] = 0;
    }
  }
  scanf("%d", &nq);
  for (q = 0; q < nq; q++) {
    scanf("%d %d", &l, &r);
    cntn = findtr(l - 1, r - 1, 1, ntree);
    gcdant = cntn.first;
    minant = cntn.second.first;
    surv = cntn.second.second;
    if (gcdant % minant != 0)
      printf("%d\n", r - l + 1);
    else
      printf("%d\n", r - l + 1 - surv);
  }
  return 0;
}
