#include <bits/stdc++.h>   using namespace std;   int n, t;   int s[100013];   int g[17][100013];   int lg[100013];   vector<pair<int, int> > sorted;   int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }   int find_l(int gcf, int ind) {     int left = 0, right = sorted.size() - 1;     while (left < right) {       int mid = (left + right) / 2;       if (sorted[mid].first == gcf && sorted[mid].second == ind) {         break;       }       if (sorted[mid].first < gcf ||           (sorted[mid].first == gcf && sorted[mid].second < ind)) {         left = mid + 1;       } else {         right = mid;       }     }     return (left + right) / 2;   }   int find_r(int gcf, int ind) {     int left = 0, right = sorted.size() - 1;     while (left < right) {       int mid = (left + right + 1) / 2;       if (sorted[mid].first == gcf && sorted[mid].second == ind) {         break;       }       if (sorted[mid].first < gcf ||           (sorted[mid].first == gcf && sorted[mid].second < ind)) {         left = mid;       } else {         right = mid - 1;       }     }     return (left + right + 1) / 2;   }   int query(int l, int r) {     int tmp = l;     int gcf = 0;     for (int i = 16; i >= 0; i--)       if ((r - l + 1) & (1 << i)) {         gcf = gcd(gcf, g[i][l]), l = l + (1 << i);       }     l = tmp;     vector<pair<int, int> >::iterator left =         lower_bound(sorted.begin(), sorted.end(), make_pair(gcf, l));     vector<pair<int, int> >::iterator right =         upper_bound(sorted.begin(), sorted.end(), make_pair(gcf, r));     return r - l + 1 - max(0, (int)(right - left));   }   int main() {     scanf( %d , &n);     int l = 0;     for (int i = 1; i <= n; i++) {       scanf( %d , &s[i]);       sorted.push_back(make_pair(s[i], i));       if (i == (1 << (l + 1))) l++;       lg[i] = l;     }     sort(sorted.begin(), sorted.end());     for (int i = 1; i <= n; i++) {       g[0][i] = s[i];     }     for (int i = 1; i <= 16; i++) {       for (int j = 1; j <= n; j++) {         g[i][j] = gcd(g[i - 1][j], g[i - 1][min(n, j + (1 << (i - 1)))]);       }     }     scanf( %d , &t);     for (int i = 0; i < t; i++) {       int l, r;       scanf( %d%d , &l, &r);       printf( %d n , query(l, r));     }   }   