mxqz 卡常

#include<bits/stdc++.h>
#define il inline
using namespace std;
il int read()
{
    int xr=0,F=1; char cr;
    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
    while(cr>='0'&&cr<='9') 
        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
    return xr*F;
}
typedef long long ll;
const int N=1e6+5;
int n,p[N],pos[N];
ll ans[N],f[N];
struct node{int l,r,id;};
vector<node> q[N];
vector<int> P[N],d[N];
struct BIT
{
    ll tr[N];
    il void add(int x,ll k) {for(;x<=n;x+=x&-x) tr[x]+=k;}
    il ll query(int x) {ll res=1;for(;x;x-=x&-x) res+=tr[x];return res;}
    il ll ask(int l,int r) {return query(r)-query(l-1);}
}tr;
il void solve()
{
    n=read(); int Q=read();
    for(int i=1;i<=n;i++) p[i]=read(),pos[p[i]]=i,tr.tr[i]=0,q[i].clear(),d[i].clear(),P[i].clear();
    for(int i=1;i<=n;i++)
        for(int j=1;j*i<=n;j++) d[j*i].push_back(i);
    for(int i=1;i<=Q;i++)
    {
        int l=read(),r=read();
        q[l].push_back({l,r,i});
    }
    for(int i=n;i;i--)
    {
        int x=p[i];
        vector<int> v;
        for(auto x:d[p[i]]) P[x].push_back(p[i]);
        for(auto x:P[p[i]]) v.push_back(pos[x]);
        sort(v.begin(),v.end());
        for(auto x:v) f[x]=0;
        f[i]=1;
        // for(auto x:v) c out<<x<<" "; cout<<endl;
        for(auto x:v) 
            for(auto y:P[p[x]]) if(pos[y]>x) f[pos[y]]+=f[x];
        for(auto x:v) tr.add(x,f[x]);
        for(auto [l,r,id]:q[i]) ans[id]=tr.ask(l,r);
    }
    for(int i=1;i<=Q;i++) printf("%lld ",ans[i]); printf("\n");
}
signed main() {int T=read();while(T--) solve();}
/*
https://www.luogu.com.cn/problem/CF1946F
start thinking at 08:30
start coding at 09:15
*/
/*
1
3 3
3 2 1
1 2
1 3
2 3
*/