#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define pir pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=100010,M=1000010;
inline int re()
{
    char c=getchar();
    int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int n,m;
int a[N];
int st[N][23];
vector<pir> qs[N];
int query(int l,int r)
{
    if(l==0) return -1;
    int d=__lg(r-l+1);
    return st[l][d]|st[r-(1<<d)+1][d];
}
int res[M];

const int K=2000010;
bool mk[K];
int pr[K],cnt;
void init()
{
    mk[0]=mk[1]=1;
    int up=2000000;
    for(int i=2;i<=up;i++)
    {
        if(mk[i]==0) pr[++cnt]=i;
        for(int j=1;j<=cnt&&pr[j]*i<=up;j++)
        {
            mk[pr[j]*i]=1;
            if(i%pr[j]==0) break;
        }
    }
}

struct node
{
    int val,tag;
};
namespace Seg
{
    #define ls (p<<1)
    #define rs (p<<1|1)
    node st[N<<2];
    void push_up(int p){st[p].val=st[ls].val+st[rs].val;}
    void push_down(int p,int l,int r)
    {
        if(st[p].tag==0) return;
        int mid=(l+r)>>1;
        st[ls].val+=(mid-l+1)*st[p].tag;
        st[ls].tag+=st[p].tag;
        st[rs].val+=(r-mid)*st[p].tag;
        st[rs].tag+=st[p].tag;
        st[p].tag=0;
        return;
    }
    void add(int ql,int qr,int z,int l=1,int r=n+1,int p=1)
    {
        if(ql<=l&&r<=qr)
        {
            st[p].val+=(r-l+1)*z;
            st[p].tag+=z;
            return;
        }
        push_down(p,l,r);
        int mid=(l+r)>>1;
        if(ql<=mid) add(ql,qr,z,l,mid,ls);
        if(mid<qr) add(ql,qr,z,mid+1,r,rs);
        push_up(p);
        return;
    }
    int query(int ql,int qr,int l=1,int r=n+1,int p=1)
    {
        if(ql<=l&&r<=qr) return st[p].val;
        push_down(p,l,r);
        int mid=(l+r)>>1,ans=0;
        if(ql<=mid) ans+=query(ql,qr,l,mid,ls);
        if(mid<qr) ans+=query(ql,qr,mid+1,r,rs);
        return ans;
    }
}
signed main()
{
    freopen("Jelly.in","r",stdin);
    freopen("Jelly.out","w",stdout);
    init();
    n=re();m=re();
    for(int i=1;i<=n;i++) a[i]=st[i][0]=re();
    for(int k=1;k<=19;k++) for(int i=1;i+(1<<k)-1<=n;i++) st[i][k]=st[i][k-1]|st[i+(1<<(k-1))][k-1];
    for(int i=1;i<=m;i++)
    {
        int l=re(),r=re();
        qs[r].pb(mp(l,i));
    }
    for(int i=1;i<=n;i++)
    {
        int pos=i;
        while(pos)
        {
            int l=0,r=pos-1,mid;
            while(l<r)
            {
                mid=(l+r+1)>>1;
                if(query(mid,i)!=query(pos,i)) l=mid;
                else r=mid-1;
            }
            if(mk[query(pos,i)]==0)
            {
                //l+1~pos
                Seg::add(1,1,pos-l);
                Seg::add(l+2,pos+1,-1);
            }
            pos=l;
        }
        for(pir tmp:qs[i]) res[tmp.se]=Seg::query(1,tmp.fi);
    }
    for(int i=1;i<=m;i++) printf("%lld\n",res[i]);
    return 0;
}