#include <bits/stdc++.h>
using namespace std;
struct MinTreeNode {
  int min;
  int count;
};
int n;
MinTreeNode tmin[200000];
int tgcd[200000];
int gcd(int a, int b) {
  if (a == 0) {
    return b;
  }
  if (b == 0) {
    return a;
  }
  if (a == 1 || b == 1) {
    return 1;
  }
  if (a % 2 == 0) {
    if (b % 2 == 0) {
      return 2 * gcd(a / 2, b / 2);
    } else {
      return gcd(a / 2, b);
    }
  } else {
    if (b % 2 == 0) {
      return gcd(a, b / 2);
    } else {
      return gcd(min(a, b), max(a, b) - min(a, b));
    }
  }
}
void buildGcdTree() {
  for (int i = n - 1; i >= 1; --i) {
    tgcd[i] = gcd(tgcd[i << 1], tgcd[i << 1 | 1]);
  }
}
void buildMinTree() {
  for (int i = n - 1; i >= 1; --i) {
    if (tmin[i << 1].min < tmin[i << 1 | 1].min) {
      tmin[i] = tmin[i << 1];
    } else {
      if (tmin[i << 1].min > tmin[i << 1 | 1].min) {
        tmin[i] = tmin[i << 1 | 1];
      } else {
        tmin[i].min = tmin[i << 1].min;
        tmin[i].count = tmin[i << 1].count + tmin[i << 1 | 1].count;
      }
    }
  }
}
MinTreeNode minAndCount(int l, int r) {
  MinTreeNode result;
  result.min = 2000000000;
  result.count = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      if (result.min == tmin[l].min) {
        result.count += tmin[l].count;
      } else {
        if (result.min > tmin[l].min) {
          result = tmin[l];
        }
      }
      ++l;
    }
    if (r & 1) {
      --r;
      if (result.min == tmin[r].min) {
        result.count += tmin[r].count;
      } else {
        if (result.min > tmin[r].min) {
          result = tmin[r];
        }
      }
    }
  }
  return result;
}
int gcdOfInterval(int l, int r) {
  int result = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      result = gcd(result, tgcd[l++]);
    }
    if (r & 1) {
      result = gcd(result, tgcd[--r]);
    }
  }
  return result;
}
int elementsThatDivideIntervalCount(int l, int r) {
  int g = gcdOfInterval(l, r);
  MinTreeNode m = minAndCount(l, r);
  if (m.min == g) {
    return m.count;
  } else {
    return 0;
  }
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i = n; i < 2 * n; ++i) {
    int s;
    cin >> s;
    tgcd[i] = s;
    tmin[i].min = s;
    tmin[i].count = 1;
  }
  buildMinTree();
  buildGcdTree();
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    int l, r;
    cin >> l >> r;
    --l;
    cout << r - l - elementsThatDivideIntervalCount(l, r) << "\n";
  }
  return 0;
}
