#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
inline void remax(T1& A, T2 B) {
  if (A < B) A = B;
}
template <class T1, class T2>
inline void remin(T1& A, T2 B) {
  if (A > B) A = B;
}
string ToString(long long num) {
  string ret;
  bool neg = false;
  if (num < 0) num *= ~0, neg = true;
  do {
    ret += ((num % 10) + '0');
    num /= 10;
  } while (num);
  if (neg) ret += '-';
  reverse(ret.begin(), ret.end());
  return ret;
}
long long ToNumber(string s) {
  long long r = 0, p = 1;
  int e = (s[0] == '-');
  for (int i = (int)s.size() - 1; i >= e; --i) r += (s[i] - '0') * p, p *= 10;
  if (e) r *= ~0;
  return r;
}
long long Gcd(long long a, long long b) {
  if (!a || !b) return a + b;
  while (a %= b ^= a ^= b ^= a)
    ;
  return b;
}
long long Power(long long base, unsigned long long power) {
  long long ret = 1;
  while (power) {
    if (power & 1) ret *= base;
    power >>= 1;
    base *= base;
  }
  return ret;
}
long long PowerMod(long long base, unsigned long long power, long long mod) {
  if (!power) return 1 % mod;
  if (power & 1) return (base * PowerMod(base, power - 1, mod)) % mod;
  return PowerMod((base * base) % mod, power >> 1, mod);
}
int Log(long long num, long long base) {
  int ret = 0;
  while (num) {
    ++ret;
    num /= base;
  }
  return ret;
}
int tree[(2 << 17) - 1];
int arr[100000];
void build(int ind, int l, int r) {
  if (l == r) {
    tree[ind] = arr[l];
    return;
  }
  int m = l + r >> 1;
  build(ind + ind + 1, l, m);
  build(ind + ind + 2, m + 1, r);
  tree[ind] = Gcd(tree[ind + ind + 1], tree[ind + ind + 2]);
}
int query(int ind, int l, int r, int a, int b) {
  if (l > b || r < a) return 0;
  if (l >= a && r <= b) return tree[ind];
  int m = l + r >> 1;
  return Gcd(query(ind + ind + 1, l, m, a, b),
             query(ind + ind + 2, m + 1, r, a, b));
}
inline void run() {
  vector<pair<int, int>> vec;
  int n, m;
  scanf("%d", &n);
  for (int i = 0; i < n;) scanf("%d", arr + i++);
  for (int i = 0; i < n; ++i) vec.emplace_back(arr[i], i);
  sort(vec.begin(), vec.end());
  build(0, 0, n - 1);
  scanf("%d", &m);
  while (m--) {
    int a, b, ans, g;
    scanf("%d%d", &a, &b);
    g = query(0, 0, n - 1, --a, --b);
    ans = b - a + 1;
    ans -=
        (upper_bound(vec.begin(), vec.end(), make_pair(g, b)) - vec.begin()) -
        (upper_bound(vec.begin(), vec.end(), make_pair(g, a - 1)) -
         vec.begin());
    printf("%d\n", ans);
  }
}
int main() {
  run();
  return 0;
}
