#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int MAXN=1e6+5;
int fac[MAXN];
struct SegmentTree{
    int l,r,gcd;
}tr[MAXN<<4];
void update(int rt)
{
    tr[rt].gcd=__gcd(tr[ls].gcd,tr[rs].gcd);
}
void build(int l,int r,int rt)
{
    tr[rt].l=l,tr[rt].r=r;
    tr[rt].gcd=0;
    if(l==r) return;
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    update(rt);
}
void modify(int pos,int rt,int c)
{
    if(tr[rt].l==tr[rt].r)
    {
        tr[rt].gcd=c;
        return;
    }
    int mid=tr[rt].l+tr[rt].r>>1;
    if(pos<=mid) modify(pos,ls,c);
    else modify(pos,rs,c);
    update(rt);
}
vector<int> len(MAXN<<3);
void solve()
{   
    fill(len.begin(),len.end(),0);
    int n,q;
    cin>>n>>q;
    vector<int> pos[n+1];
    vector<int> a(n+2);
    multiset<pair<int,int>> st;
    int cnt=0,tmp=0;
    for(int i=1;i<=n;i++)
    {
        tmp++;
        cin>>a[i];
        if(a[i]<a[i-1])
        {
            len[++cnt]=tmp-1;
            pos[tmp-1].push_back(cnt);
            st.insert({i-tmp+1,i-1});
            tmp=1;
        }
    }
    a[0]=1e18;
    len[++cnt]=tmp;
    pos[tmp].push_back(cnt);
    st.insert({n-tmp+1,n});
    // for(auto [x,y]:st) cerr<<x<<' '<<y<<endl;

    // for(int i=1;i<=cnt;i++) cerr<<len[i]<<' ';
    // cerr<<endl;
    // for(int i=1;i<=n;i++)
    // {
    //     for(auto x:pos[i]) cerr<<x<<' ';
    //     cerr<<endl;
    // }
    const int maxn=1000000;
    build(1,maxn,1);
    for(int i=1;i<=cnt;i++) modify(i,1,len[i]);
    auto del=[&](int l,int r)
    {
        if(l>r) return;
        modify(pos[r-l+1].back(),1,0);
        // cerr<<"============\n";
        len[pos[r-l+1].back()]=0;
        pos[r-l+1].pop_back();
        st.erase({l,r});
    };
    auto add=[&](int l,int r)
    {
        if(l>r) return;
        len[++cnt]=r-l+1;
        modify(cnt,1,len[cnt]);
        pos[len[cnt]].push_back(cnt);
        st.insert({l,r});
    };
    auto query=[&]
    {
        auto [L,R]=*st.rbegin();
        modify(pos[R-L+1].back(),1,0);
        int ans1=tr[1].gcd;
        modify(pos[R-L+1].back(),1,R-L+1);
        if(ans1==0) return n;
        else return fac[ans1];
    };
    cout<<query()<<endl;
    while(q--)
    {
        int p,x;
        cin>>p>>x;
        auto [l,r]=*prev(st.upper_bound({p,1e18}));
        auto [L,R]=*prev(st.upper_bound({p-1,1e18}));
        del(l,r);
        a[p]=x;
        // cerr<<"===========\n";
        // cerr<<l<<' '<<r<<endl;
        // cerr<<L<<' '<<R<<endl;
        if(a[p]>=a[p-1])
        {
            // cout<<l<<' '<<r<<endl;
            // cout<<L<<' '<<R<<endl;
            if(l==L && r==R) add(l,r);
            else
            {
                del(L,R);
                add(L,r);
            }
        }
        else
        {
            if(l==L && r==R) {add(L,p-1);add(p,r);}
            else add(l,r);
        }
        // for(int i=1;i<=cnt;i++) cerr<<len[i]<<' ';
        // cerr<<endl;
        auto [ll,rr]=*prev(st.upper_bound({p,1e18}));
        auto [LL,RR]=*prev(st.upper_bound({p+1,1e18}));
        // cerr<<ll<<' '<<rr<<endl;
        // cerr<<LL<<' '<<RR<<endl;
        del(ll,rr);
        if(a[p]<=a[p+1])
        {
            // cerr<<ll<<' '<<rr<<endl;
            // cerr<<LL<<' '<<RR<<endl;
            if(ll==LL && rr==RR) add(ll,rr);
            else
            {
                del(LL,RR);
                add(ll,RR);
            }
        }
        else 
        {
            if(ll==LL && rr==RR) {add(p+1,R);add(ll,p);}
            else add(ll,rr);
        }
        cout<<query()<<endl;
        // for(int i=1;i<=cnt;i++) cerr<<len[i]<<' ';
        // cerr<<endl;
    }
}
signed main()
{
    for(int i=1;i<MAXN;i++)
        for(int j=i;j<MAXN;j+=i) fac[j]++;

    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}