#include<bits/stdc++.h>
#define N 200010
using namespace std;
struct node
{
    int l,r,id;
};

int prime[N],w[N],b[N],l[N],r[N],ans[N],tree[N];
node q[N];
vector<int> factor[N],v[N];
int n,m;

void get_prime()
{
    for (int i=2;i<N;i++)
    {
        if (!prime[i]) prime[++prime[0]]=i;
        for (int j=1;j<=prime[0]&&prime[j]*i<N;j++)
        {
            prime[prime[j]*i]=1;
            if (i%prime[j]==0) break;
        }
    }
}

void getfactors(int k)
{
    factor[k].clear();
    int x=w[k];
    for (int i=1;prime[i]*prime[i]<=x;i++)
        if (x%prime[i]==0)
    {
        factor[k].push_back(prime[i]);
        while(x%prime[i]==0) x/=prime[i];
    }
    if (x!=1) factor[k].push_back(x);
}

bool cmp(node a, node b)
{
    return a.l<b.l;
}

int lowbit(int a)
{
    return (a)&(-a);
}

int sum(int a)
{
    int s=0;
    while (a>0)
    {
        s+=tree[a];
        a-=lowbit(a);
    }
    return s;
}

void update(int a,int b)
{
    while (a<=n)
    {
        tree[a]+=b;
        a+=lowbit(a);
    }
}

int main()
{
    get_prime();
    while(scanf("%d%d",&n,&m)!=EOF&&n!=0&&m!=0)
    {
        for (int i=0;i<=n;i++) v[i].clear();
        for (int i=0;i<=n;i++) tree[i]=0;

        for (int i=1;i<=n;i++) scanf("%d",&w[i]);
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q+1,q+m+1,cmp);

        for (int i=1;i<=n;i++) getfactors(i);
        for (int i=1;i<N;i++) b[i]=0;
        for (int i=1;i<=n;i++)
        {
            int tmp=0;
            for (int j=0;j<(int)factor[i].size();j++)
            {
                tmp=max(tmp,b[factor[i][j]]);
                b[factor[i][j]]=i;
            }
            l[i]=tmp;
            v[l[i]].push_back(i);
        }
        for (int i=1;i<N;i++) b[i]=n+1;
        for (int i=n;i>=1;i--)
        {
            int tmp=n+1;
            for (int j=0;j<(int)factor[i].size();j++)
            {
                tmp=min(tmp,b[factor[i][j]]);
                b[factor[i][j]]=i;
            }
            if (tmp==n+1) r[i]=0; else r[i]=tmp;
        }

        int cur=1;
        for (int i=0;i<=n;i++)
        {
            while(cur<=m&&q[cur].l==i)
            {
                ans[q[cur].id]=sum(q[cur].r)-sum(q[cur].l-1);
                cur++;
            }
            for (int j=0;j<v[i].size();j++)
            {
                update(v[i][j],1);
                if (r[v[i][j]]!=0) update(r[v[i][j]],-1);
            }
            if (r[i]!=0) update(r[i],1);
        }
        for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}