#include <bits/stdc++.h>
using namespace std;
struct Z {
  int g, m, k;
};
int N, Q, x, l, r, j;
Z T[240005][18], n;
int gcd(int a, int b) {
  for (int n; b; n = a % b, a = b, b = n)
    ;
  return a;
}
Z g(Z a, Z b) {
  if (a.g < 1) return b;
  if (b.g < 1) return a;
  return {gcd(a.g, b.g), a.m < b.m ? a.m : b.m,
          a.m < b.m   ? a.k
          : b.m < a.m ? b.k
                      : a.k + b.k};
}
int main() {
  cin >> N;
  for (int i = (1); i <= (N); i++) {
    cin >> x;
    T[i][0] = {x, x, 1};
  }
  cin >> Q;
  for (int j = (1); j <= (17); j++)
    for (int i = (1); i <= (N); i++)
      T[i][j] = g(T[i][j - 1], T[i + (1 << j - 1)][j - 1]);
  while (Q--) {
    cin >> l >> r;
    x = r - l + 1;
    n = {0, 0, 0};
    for (j = 17; j >= 0; j--)
      if (l + (1 << j) <= r + 1) {
        n = g(n, T[l][j]);
        l += 1 << j;
      }
    cout << (n.g == n.m ? x - n.k : x) << endl;
  }
  return 0;
}
