#include <bits/stdc++.h>
using namespace std;
const int maxx = 201000;
struct node {
  int val, num;
  node() { val = num = 0; }
} t[maxx << 2];
int n, m, w[maxx];
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline void pushup(int cur) {
  t[cur].val = gcd(t[cur << 1].val, t[cur << 1 | 1].val);
  if (t[cur << 1].val == t[cur].val) t[cur].num += t[cur << 1].num;
  if (t[cur << 1 | 1].val == t[cur].val) t[cur].num += t[cur << 1 | 1].num;
}
inline void build(int cur, int l, int r) {
  if (l == r) {
    t[cur].val = w[l];
    t[cur].num = 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(cur << 1, l, mid);
  build(cur << 1 | 1, mid + 1, r);
  pushup(cur);
}
inline node query(int cur, int l, int r, int L, int R) {
  if (L == l && r == R) {
    return t[cur];
  }
  int mid = (l + r) >> 1;
  if (L > mid)
    return query(cur << 1 | 1, mid + 1, r, L, R);
  else if (R <= mid)
    return query(cur << 1, l, mid, L, R);
  else {
    node ls, rs, ans;
    ls = query(cur << 1, l, mid, L, mid);
    rs = query(cur << 1 | 1, mid + 1, r, mid + 1, R);
    ans.val = gcd(ls.val, rs.val);
    if (ans.val == ls.val) ans.num += ls.num;
    if (ans.val == rs.val) ans.num += rs.num;
    return ans;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
  build(1, 1, n);
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    cout << (r - l + 1) - query(1, 1, n, l, r).num << endl;
  }
  return 0;
}
