#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAXN=5e5+7;
int t;
int n,m;
int a[MAXN];
int cnt=0,prime[MAXN];
bool vis[MAXN];
void pre()
{
    int lim=5e5;
    vis[1]=1;
    for(int i=2;i<=lim;i++)
    {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt && i*prime[j]<=lim;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    return;
}
bool check(int l,int r)
{
    for(int i=l+1;i<=r;i++)
    {
        if(a[i]<a[i-1]) return 0;
    }
    return 1;
}
int main() {

    // freopen("data.out","r",stdin);
    // freopen("std.out","w",stdout);
    cin.tie(nullptr) -> sync_with_stdio(false);
    
    pre();
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        int ans=0;
        for(int k=1;k<=n;k++)
        {
            int num=n/k;
            bool kkk=1;
            for(int i=0;i<=num;i++)
            {
                int l=i*k+1,r=(i+1)*k;
                if(l>n) break;
                r=min(r,n);
                if(!check(l,r)) {kkk=0;break;}  
            }
            if(kkk) ans++;
        }
        cout<<ans<<'\n';
        while(m--)
        {
            int loc,v;
            cin>>loc>>v;
            a[loc]=v;
            ans=0;
            for(int k=1;k<=n;k++)
            {
                int num=n/k;
                bool kkk=1;
                for(int i=0;i<=num;i++)
                {
                    int l=i*k+1,r=(i+1)*k;
                    if(l>n) break;
                    r=min(r,n);
                    if(!check(l,r)) {kkk=0;break;}  
                }
                if(kkk) ans++;
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}