#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;
}
set< pair<int,int> > s[MAXN/2];
int tot=0;
bool pd[MAXN];
int ton[MAXN];
set<int> id;
void add(int x)
{
    int lim=sqrt(x)+5;
    int sss=x;
    for(int i=1;i<=cnt;i++)
    {
        if(x>lim) break;
        if(x%prime[i]) continue;
        int numk=0;
        while(x%prime[i]==0) numk++,x/=prime[i];
        s[prime[i]].insert({numk,sss});
        if(!ton[prime[i]]) id.insert(prime[i]);
        ton[prime[i]]++;
    }
}
void del(int x)
{
    int lim=sqrt(x)+5;
    int sss=x;
    for(int i=1;i<=cnt;i++)
    {
        if(x>lim) break;
        if(x%prime[i]) continue;
        int numk=0;
        while(x%prime[i]==0) numk++,x/=prime[i];
        s[prime[i]].erase(s[prime[i]].find({numk,sss}));
        ton[prime[i]]--;
        if(!ton[prime[i]]) id.erase(prime[i]);
    }
}
int get_ans()
{
    int res=1;
    int numk=0;
    for(auto i : id)
    {
        int idk=i;
        if(s[idk].size()==tot)
        {
            auto it=s[idk].begin();
            int sumk=1,lim=(*it).first;
            for(int j=1;j<=lim;j++) sumk*=idk;
            res*=sumk;
        }
    }
    return res;
}
int get_num(int x)
{
    int res=0;
    for(int i=1;i*i<=x;i++)
    {
        if(x%i) break;
        res++;
        if(i*i==x) break;
        res++;
    }
    return res;
}
int main() {
    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];
        
        for(int i=2;i<=n;i++)
        {
            if(a[i]<a[i-1])
            {
                pd[i-1]=1;
                tot++;
                add(i-1);
            }
        }
        int ans;
        if(tot==0) ans=n;
        else ans=get_num(get_ans());
        cout<<ans<<"\n";
        while(m--)
        {
            int loc,v;
            cin>>loc>>v;
            
            if(loc>1&&a[loc]<a[loc-1])
            {
                pd[loc-1]=0;
                tot--;
                del(loc-1);
            }
            if(loc<n&&a[loc+1]<a[loc])
            {
                pd[loc]=0;
                tot--;
                del(loc);
            }
            a[loc]=v;
            if(loc>1&&a[loc]<a[loc-1])
            {
                pd[loc-1]=1;
                tot++;
                add(loc-1);
            }
            if(loc<n&&a[loc+1]<a[loc])
            {
                pd[loc]=1;
                tot++;
                add(loc);
            }
            if(tot==0) ans=n;
            else ans=get_num(get_ans());
            cout<<ans<<'\n';
        }

        tot=0;
        for(int i=0;i<=n;i++)
        {
            pd[i]=0;ton[i]=0;
            s[i].clear();
        }
    }
    return 0;
}