#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int q, seg[N * 4], a[N], l, r, n;
map<int, vector<int>> mp;
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void build(int n, int s, int e) {
  if (s == e) {
    seg[n] = a[s];
    return;
  }
  build(n * 2, s, (s + e) / 2);
  build(n * 2 + 1, (s + e) / 2 + 1, e);
  seg[n] = gcd(seg[n * 2], seg[n * 2 + 1]);
}
int get(int n, int s, int e) {
  if (e < l || s > r) return 0;
  if (e <= r && s >= l) return seg[n];
  return gcd(get(n * 2, s, (s + e) / 2), get(n * 2 + 1, (s + e) / 2 + 1, e));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    mp[a[i]].push_back(i);
  }
  build(1, 1, n);
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &l, &r);
    int x = get(1, 1, n);
    int low = lower_bound(mp[x].begin(), mp[x].end(), l) - mp[x].begin();
    int high = upper_bound(mp[x].begin(), mp[x].end(), r) - mp[x].begin();
    printf("%d\n", r - l + 1 - (high - low));
  }
  return 0;
}
