#include <stdio.h>  #include <string.h>  #include <iostream>  #include <algorithm>  #include <stack>  #include <vector>  #include <queue>  #include <set>  #include <map>  #include <string>  #include <math.h>  #include <stdlib.h>  #include <time.h> #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;#define PF(x) cout << "debug: " << x << " ";#define EL cout << endl;#define PC(x) puts(x);typedef long long ll;#define CLR(x, v) sizeof (x, v, sizeof(x))using namespace std;const int INF = 0x5f5f5f5f;const int maxn = 2e5 + 10;const int mod = 1e9 + 7;const double eps = acos(-1);const double PI= atan(1.0)*4;int n,q,a[maxn],tree[maxn],vis[2000000],ans[maxn];vector<pair<int,int> >gd[maxn];struct st{    int l,r,id;}qer[maxn];int gcd(int a,int b){    return b == 0?a:gcd(b,a%b);}bool cmp(st x,st y){    return x.r < y.r;}void Add(int k,int num){    while(k <= n){        tree[k] += num;        k += k&(-k);    }}int Sum(int k){    int sum = 0;    while(k > 0){        sum += tree[k];        k -= k&(-k);    }    return sum;}int main(){    freopen("in.txt","r",stdin);    while(~scanf("%d%d",&n,&q)){        for(int i = 1;i <= n;i++){            scanf("%d",&a[i]);            gd[i].clear();        }        for(int i = 1;i <= n;i++){            int x = a[i],y = i;            for(int j = 0;j <gd[i-1].size();j++){                int t = gcd(gd[i-1][j].first,a[i]);                if(t != x){                    gd[i].push_back(make_pair(x,y));                    x = t,y = gd[i-1][j].second;//x记录从y位置到当前处理的i位置的gcd值，y为相同gcd中最右边的位置，最右边这个是必须的                }            }            gd[i].push_back(make_pair(x,y));        }       for(int i = 1;i <= q;i++){            scanf("%d%d",&qer[i].l,&qer[i].r);            qer[i].id = i;       }        sort(qer + 1,qer + 1 + q,cmp);        memset(vis,0,sizeof(vis));        memset(tree,0,sizeof(tree));        int len = 1;        for(int i = 1; i <= n;i++){           // cout<<i<<":";            for(int j = 0;j < gd[i].size();j++){               // cout<<gd[i][j].first<<"->"<<gd[i][j].second<<" ";                int c1 = gd[i][j].first,c2 = gd[i][j].second;              //如果这个gcd值c1出现过则更新其位置，根据非严格递减，                             这样一定能更新为最靠近当前的i的位置                if(vis[c1] > 0)                                      Add(vis[c1],-1);                vis[c1] = c2;                Add(c2,1);            }           // cout<<endl;            while(qer[len].r == i){                ans[qer[len].id] = Sum(qer[len].r) - Sum(qer[len].l-1);                len++;            }        }        for(int i = 1;i <= q;i++)            printf("%d\n",ans[i]);    }    return 0;}