#include <bits/stdc++.h>
using namespace std;
pair<int, int> arr[1 << 18];
int gcd(int a, int b) {
  int large = max(a, b);
  int small = min(a, b);
  if (small == 0) return large;
  return gcd(small, large % small);
}
void add(int indx, int val, int curr = 0, int lower = 0,
         int upper = (1 << 17) - 1) {
  if (lower == upper) {
    arr[curr] = make_pair(val, 1);
    return;
  }
  int mid = (lower + upper) / 2;
  if (indx < mid) {
    add(indx, val, 2 * curr + 1, lower, mid);
    int g = gcd(arr[curr].first, arr[2 * curr + 1].first);
    int sum = 0;
    if (g == arr[2 * curr + 2].first) sum += arr[2 * curr + 2].second;
    if (g == arr[2 * curr + 1].first) sum += arr[2 * curr + 1].second;
    arr[curr] = make_pair(g, sum);
  } else {
    add(indx, val, 2 * curr + 2, mid + 1, upper);
    int g = gcd(arr[curr].first, arr[2 * curr + 2].first);
    int sum = 0;
    if (g == arr[2 * curr + 1].first) sum += arr[2 * curr + 1].second;
    if (g == arr[2 * curr + 2].first) sum += arr[2 * curr + 2].second;
    arr[curr] = make_pair(g, sum);
  }
  return;
}
pair<int, int> query(int lowerindx, int upperindx, int curr = 0, int lower = 0,
                     int upper = (1 << 17) - 1) {
  if (lowerindx <= lower && upperindx >= upper) return arr[curr];
  if (lower > upperindx || upper < lowerindx) return make_pair(0, 0);
  int mid = (lower + upper) / 2;
  pair<int, int> left = query(lowerindx, upperindx, 2 * curr + 1, lower, mid);
  pair<int, int> right =
      query(lowerindx, upperindx, 2 * curr + 2, mid + 1, upper);
  int g = gcd(left.first, right.first);
  int c = 0;
  if (left.first == g) c += left.second;
  if (right.first == g) c += right.second;
  return make_pair(g, c);
}
int main() {
  int N;
  cin >> N;
  int e;
  for (int i = 0; i < N; ++i) {
    cin >> e;
    add(i, e);
  }
  int T;
  cin >> T;
  int l, r;
  for (int i = 0; i < T; ++i) {
    cin >> l >> r;
    cout << (r - l + 1) - query(l, r).second << endl;
  }
  return 0;
}
