#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAXN=5e5+7;
int t;
int n,m,gcdk;
vector<int> sum[MAXN];
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;
        }
    }
    for(int i=0;i<=2e5;i++) sum[1].push_back(1);
    for(int i=1;i<=cnt;i++)
    {
        int x=prime[i];
        if(prime[i]>2e5) break;
        int sumk=1;
        sum[x].push_back(sumk);
        while(sumk<2e5)
        {
            sumk*=x;
            sum[x].push_back(sumk);
        }
    }
    return;
}
set< pair<int,int> > s[MAXN/2];
int tot=0,id[MAXN],id_num=0;
bool pd[MAXN];
int ton[MAXN];
void add(int x)
{
    int lim=sqrt(x)+5;
    int sss=x;
    for(int i=1;i<=cnt;i++)
    {
        if(prime[i]>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[++id_num]=prime[i];
        ton[prime[i]]++;
    }
    if(x!=1)
    {
            
        s[x].insert({1,sss});
        if(!ton[x]) id[++id_num]=x;
        ton[x]++;
        
    }
    return;
}
void del(int x)
{
    int lim=sqrt(x)+5;
    int sss=x;
    for(int i=1;i<=cnt;i++)
    {
        if(prime[i]>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(x!=1)
    {
        
        s[x].erase({1,sss});
        ton[x]--;
        
    }
    return;
}
int b[MAXN];
int get_ans()
{
    int res=1;
    int numk=0;
    for(int i=1;i<=id_num;i++)
    {
        int idk=id[i];
        if(s[idk].size()==0) continue;
        b[++numk]=idk;
        if(s[idk].size()==tot)
        {
            auto it=s[idk].begin();
            int lim=(*it).first;
            res*=sum[idk][lim];
        }
    }
    id_num=numk;
    for(int i=1;i<=numk;i++) id[i]=b[i];
    return res;
}
int get_num(int x)
{
    int res=0;
    for(int i=1;i*i<=x;i++)
    {
        if(x%i) continue;
        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];
        gcdk=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]<a[i-1])
            {
                pd[i-1]=1;
//                cerr<<i-1<<" asd"<<endl;
                add(i-1);tot++;
            }
        }
        
        int ans;
        if(tot==0) ans=n,gcdk=1;
        else ans=get_num(get_ans());
        
        cout<<ans<<"\n";
//        cerr<<ton[2]<<" as"<<tot<<" asd"<<endl;
        while(m--)
        {
            int loc,v;
            cin>>loc>>v;
            
            if(loc>1&&a[loc]<a[loc-1])
            {
                pd[loc-1]=0;
                del(loc-1);tot--;
            }
            
//            cerr<<gcdk<<"  adasdasd"<<endl;
            if(loc<n&&a[loc+1]<a[loc])
            {
                pd[loc]=0;
                del(loc);tot--;
            }
            a[loc]=v;
            if(loc>1&&a[loc]<a[loc-1])
            {
                pd[loc-1]=1;
                add(loc-1);tot++;
            }
            if(loc<n&&a[loc+1]<a[loc])
            {
                pd[loc]=1;
                add(loc);tot++;
            }
            if(tot==0) ans=n,gcdk=1;
            else ans=get_num(get_ans());
            cout<<ans<<'\n';
        }
        tot=0;gcdk=1;
        id_num=0;
        for(int i=0;i<=n;i++)
        {
            pd[i]=0;ton[i]=0;
            s[i].clear();
        }
    }
    return 0;
}