#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
inline int gcd(int a, int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
inline long long power(long long a, long long n, long long m) {
  if (n == 0) return 1;
  long long p = power(a, n / 2, m);
  p = (p * p) % m;
  if (n % 2)
    return (p * a) % m;
  else
    return p;
}
const long long MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
int st[1000000];
int s[100001];
vector<int> sg[1000000];
int g;
void constructtree(int i, int l, int r) {
  if (r < l) return;
  if (l == r) {
    st[i] = s[l];
    return;
  }
  int m = (l + r) / 2;
  constructtree(2 * i + 1, l, m);
  constructtree(2 * i + 2, m + 1, r);
  st[i] = gcd(st[2 * i + 1], st[2 * i + 2]);
}
int query(int i, int l, int r, int qs, int qe) {
  if (qs > r || qe < l) return 0;
  if (qs <= l && qe >= r) return st[i];
  int m = (l + r) / 2;
  return gcd(query(2 * i + 1, l, m, qs, qe),
             query(2 * i + 2, m + 1, r, qs, qe));
}
int query2(int i, int l, int r, int qs, int qe) {
  if (qs > r || qe < l) return 0;
  if (qs <= l && qe >= r) {
    return (upper_bound(sg[i].begin(), sg[i].end(), g) -
            lower_bound(sg[i].begin(), sg[i].end(), g));
  }
  int m = (l + r) / 2;
  return query2(2 * i + 1, l, m, qs, qe) + query2(2 * i + 2, m + 1, r, qs, qe);
}
void merge(int i1, int i2, int i3) {
  int n1 = sg[i2].size();
  int n2 = sg[i3].size();
  int i = 0, j = 0;
  while (i < n1 && j < n2) {
    if (sg[i2][i] <= sg[i3][j]) {
      sg[i1].push_back(sg[i2][i]);
      i++;
    } else {
      sg[i1].push_back(sg[i3][j]);
      j++;
    }
  }
  while (i < n1) {
    sg[i1].push_back(sg[i2][i]);
    i++;
  }
  while (j < n2) {
    sg[i1].push_back(sg[i3][j]);
    j++;
  }
}
void constructsortedtree(int i, int l, int r) {
  if (r < l) return;
  if (l == r) {
    sg[i].push_back(s[l]);
    return;
  }
  int m = (l + r) / 2;
  constructsortedtree(2 * i + 1, l, m);
  constructsortedtree(2 * i + 2, m + 1, r);
  merge(i, 2 * i + 1, 2 * i + 2);
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int n, t, l, r;
  int ans;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  constructtree(0, 0, n - 1);
  constructsortedtree(0, 0, n - 1);
  cin >> t;
  while (t--) {
    cin >> l >> r;
    l--;
    r--;
    g = query(0, 0, n - 1, l, r);
    ans = query2(0, 0, n - 1, l, r);
    cout << r - l + 1 - ans << "\n";
  }
  return 0;
}
