#include <bits/stdc++.h>
using namespace std;
double PI = 3.141592653589793;
const double EPS = 1e-9;
const int N = 1e6 + 5;
const long long mod = 1e9 + 7;
const int oo = 1e9;
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
int seg[4 * 100005], t[100005];
int n, q;
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] = t[s];
    return;
  }
  build(2 * n, s, (s + e) / 2);
  build(2 * n + 1, (s + e) / 2 + 1, e);
  seg[n] = GCD(seg[2 * n], seg[2 * n + 1]);
}
int get(int n, int s, int e, int l, int r) {
  if (s > r || e < l) return -1;
  if (s >= l && e <= r) return seg[n];
  int a = get(2 * n, s, (s + e) / 2, l, r);
  int b = get(2 * n + 1, (s + e) / 2 + 1, e, l, r);
  if (a == -1) return b;
  if (b == -1) return a;
  return GCD(a, b);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &t[i]);
    mp[t[i]].push_back(i);
  }
  build(1, 1, n);
  scanf("%d", &q);
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    int g = get(1, 1, n, l, r);
    auto it1 = lower_bound(mp[g].begin(), mp[g].end(), l);
    auto it2 = upper_bound(mp[g].begin(), mp[g].end(), r);
    int x = it2 - it1;
    printf("%d\n", r - l + 1 - x);
  }
}
