#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
const int INF = 0x3f3f3f3f;
const int LG = 19;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int n;
int P[N];
int dp[LG][N];
int off = 1;
int lo;
int hi;
int POT[N];
struct node {
  int val;
  int how;
  node() {
    val = INF;
    how = 0;
  }
} T[(1 << 19) + 10], F;
inline void load() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &P[i]), dp[0][i] = P[i];
  for (int i = 1; i < LG; i++) {
    for (int j = 0; j < n; j++) {
      int pot = (1 << (i - 1));
      dp[i][j] = dp[i - 1][j];
      if (pot >= n) continue;
      dp[i][j] = gcd(dp[i][j], dp[i - 1][j + pot]);
    }
  }
  int potencija = 1;
  int na_koju = 0;
  for (int i = 1; i < N; i++) {
    while (potencija * 2 <= i) potencija *= 2, na_koju++;
    POT[i] = na_koju;
  }
}
int get(int x, int y) {
  int len = y - x + 1;
  return gcd(dp[POT[len]][x], dp[POT[len]][y - (1 << POT[len]) + 1]);
}
inline node merge(node A, node B) {
  node C;
  if (A.val < B.val)
    C = A;
  else if (B.val < A.val)
    C = B;
  else
    C.val = A.val, C.how = A.how + B.how;
  return C;
}
node query(int a, int b, int node) {
  if (a > hi || b < lo) return F;
  if (a >= lo && b <= hi) return T[node];
  return merge(query(a, (a + b) / 2, node * 2),
               query((a + b) / 2 + 1, b, node * 2 + 1));
}
inline void solve() {
  while (off < n) off <<= 1;
  for (int i = 0; i < n; i++) T[i + off].val = P[i], T[i + off].how = 1;
  for (int i = off - 1; i >= 1; i--) T[i] = merge(T[i * 2], T[i * 2 + 1]);
  int q;
  scanf("%d", &q);
  while (q--) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    int GCD = get(x, y);
    lo = x;
    hi = y;
    node A = query(0, off - 1, 1);
    if (A.val == GCD)
      printf("%d\n", y - x + 1 - A.how);
    else
      printf("%d\n", y - x + 1 + 0);
  }
}
int main(void) {
  load();
  solve();
  return 0;
}
