#include <bits/stdc++.h>
using namespace std;
int n, a[100001], t, l, r;
int _gcd[262144][19], _min[262144][19], _num[262144][19];
int gcd(int x, int y) {
  if (x < y) swap(x, y);
  if (y == 0) return x;
  int r = x % y;
  return gcd(y, r);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) {
    _min[i][0] = a[i];
    _gcd[i][0] = a[i];
    _num[i][0] = 1;
  }
  for (int k = 1; k <= 18; k++) {
    for (int i = 1; i <= n; i++) {
      if (_min[i][k - 1] == _min[i + (1 << (k - 1))][k - 1]) {
        _min[i][k] = _min[i][k - 1];
        _num[i][k] = _num[i][k - 1] + _num[i + (1 << (k - 1))][k - 1];
      } else if (_min[i][k - 1] < _min[i + (1 << (k - 1))][k - 1]) {
        _min[i][k] = _min[i][k - 1];
        _num[i][k] = _num[i][k - 1];
      } else {
        _min[i][k] = _min[i + (1 << (k - 1))][k - 1];
        _num[i][k] = _num[i + (1 << (k - 1))][k - 1];
      }
    }
  }
  for (int k = 1; k <= 18; k++)
    for (int i = 1; i <= n; i++)
      _gcd[i][k] = gcd(_gcd[i][k - 1], _gcd[i + (1 << (k - 1))][k - 1]);
  scanf("%d", &t);
  for (int j = 1; j <= t; j++) {
    scanf("%d", &l);
    scanf("%d", &r);
    int tmp = r - l + 1;
    int k = log2(r - l + 1);
    int GCD = gcd(_gcd[l][k], _gcd[r - (1 << k) + 1][k]);
    int ans = 0;
    int pos = l;
    for (int i = 0; i <= 20; i++) {
      if ((tmp & (1 << i)) > 0) {
        if (_min[pos][i] == GCD) ans += _num[pos][i];
        pos += (1 << i);
      }
    }
    printf("%d\n", tmp - ans);
  }
}
