#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define endl "\n"

const int N=1e6+100;
#define MAX 1e6
ll nu[N],len[N];

#define ls (n<<1)
#define rs (n<<1|1)

ll t[N<<2],lazy[N<<2];

ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}

void pushup(int n)
{
    t[n]=gcd(t[ls],t[rs]);
}

void pushdown(int n)
{
    if(lazy[n])
    {
        lazy[ls]=lazy[rs]=lazy[n];
        t[ls]=t[rs]=lazy[n];
        lazy[n]=0;
    }
}

bool flag[N];

void create(int n,int l,int r)
{
    if(l==r)
    {
        t[n]=len[l];
        lazy[n]=0;
        return ;
    }
    int mi=l+r>>1;
    create(ls,l,mi);
    create(rs,mi+1,r);
    pushup(n);
}

void update(int n,int l,int r,int sl,int sr,int w)
{
    if(l>sr||r<sl)
    {
        return ;
    }
    if(l>=sl&&r<=sr)
    {
        t[n]=w;
        lazy[n]=w;
        return ;
    }
    int mi=l+r>>1;
    pushdown(n);
    update(ls,l,mi,sl,sr,w);
    update(rs,mi+1,r,sl,sr,w);
    pushup(n);
}

ll answer(int n,int l,int r,int sl,int sr)
{
    if(l>sr||r<sl)
    {
        return 0;
    }
    if(l>=sl&&r<=sr)
    {
        return t[n];
    }
    int mi=l+r>>1;
    pushdown(n);
    ll g=0;
    g=gcd(g,answer(ls,l,mi,sl,sr));
    g=gcd(g,answer(rs,mi+1,r,sl,sr));
    return g;
}

set<pair<int,int>>s;

vector<ll>p;

ll an(ll n)
{
    ll ans=1;
    for(auto i:p)
    {
        if(i*i>n)
        {
            break;
        }
        int nu=0;
        while(n%i==0)
        {
            nu++;
            n/=i;
        }
        ans*=nu+1;
    }
    if(n!=1)
    {
        ans*=2;
    }
    return ans;
}

int main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    for(int i=2;i<=MAX;i++)
    {
        if(!flag[i])
        {
            p.push_back(i);
        }
        for(auto j:p)
        {
            if(i*j>=MAX)
            {
                break;
            }
            flag[i*j]=1;
            if(i%j==0)
            {
                break;
            }
        }
    }
    int T;
    cin>>T;
    while(T--)
    {
        s.clear();
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>nu[i];
        }
        for(int i=1;i<=n;i++)
        {
            int j=i;
            while(j+1<=n&&nu[j+1]>=nu[j])
            {
                j++;
            }
            for(int k=i;k<=j;k++)
            {
                len[k]=j-i+1;
            }
            s.insert({i,j});
            i=j;
        }
        create(1,1,n);
        auto end=--s.upper_bound({n,MAX});
        if(end->first==1)
        {
            cout<<n<<endl;
        }
        else
        cout<<an(answer(1,1,n,1,end->first-1))<<endl;
        for(int i=1;i<=m;i++)
        {
            int id,v;
            cin>>id>>v;
            nu[id]=v;
            auto sign=--s.upper_bound({id,MAX});
            int l=sign->first,r=sign->second;
            s.erase(sign);
            if(l!=id)
            s.insert({l,id-1});
            if(r!=id)
            {
                s.insert({id+1,r});
            }
            s.insert({id,id});
            sign=--s.upper_bound({id,MAX});
            l=sign->first,r=sign->second;
            auto signl=sign;
            auto signr=sign;
            int ll,rr;
            if(l==1)
            {
                ll=1;
            }
            else
            {   

                signl--;
                ll=signl->first;
            }
            if(r==n)
            {
                rr=n;
            }
            else
            {   
      
                signr++;
                rr=signr->second;
            }
            if(l!=ll&&nu[l]>=nu[l-1]&&r!=rr&&nu[r]<=nu[r+1])
            {
                s.erase(sign);
                s.erase(signl);
                s.erase(signr);
                s.insert({ll,rr});
            }
            else if(l!=ll&&nu[l]>=nu[l-1])
            {
                s.erase(sign);
                s.erase(signl);
                s.insert({ll,r});
            }
            else if(r!=rr&&nu[r]<=nu[r+1])
            {
                s.erase(sign);
                s.erase(signr);
                s.insert({l,rr});
            }
            signl=--s.upper_bound({ll,MAX});
            signr=s.upper_bound({rr,MAX});
            for(auto i=signl;i!=signr;i++)
            {
                update(1,1,n,i->first,i->second,i->second-i->first+1);
            }
            end=--s.upper_bound({n,MAX});
            if(end->first==1)
            {
                cout<<n<<endl;
                continue;
            }
            cout<<an(answer(1,1,n,1,end->first-1))<<endl;
        }

    }
    return 0;
}