#include<bits/stdc++.h>
#define int long long
#define N 500007
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int T,n,q,a[N];
int ys[N];
void pre()
{
    for(int i=1;i<N;i++)
    {
        ys[i]=0;
    }
    for(int i=1;i<N;i++)
    {
        for(int j=i;j<N;j+=i)
        {
            ys[j]++;
        }
    }
}
struct segment_tree
{
    int gd[N<<2],tg[N<<2];
    set<int>st;
    void pu(int i)
    {
        gd[i]=gcd(gd[i<<1],gd[i<<1|1]);
    }
    void pd(int i)
    {
        if(tg[i]<0)
        {
            return ;
        }
        gd[i<<1]=gcd(gd[i<<1],tg[i]);
        gd[i<<1|1]=gcd(gd[i<<1|1],tg[i]);
        tg[i<<1]=gcd(tg[i<<1],tg[i]);
        tg[i<<1|1]=gcd(tg[i<<1|1],tg[i]);
        tg[i]=-1;
    }
    void bd(int i,int l,int r)
    {
        if(l==r)
        {
            gd[i]=0;
        }
        else
        {
            int mid=(l+r)>>1;
            bd(i<<1,l,mid);
            bd(i<<1|1,mid+1,r);
            pu(i);
        }
    }
    void up(int x,int L,int R,int i,int l,int r)
    {
        if(L<=l&&r<=R)
        {
            gd[i]=x;
            tg[i]=x;
        }
        else
        {
            int mid=(l+r)>>1;
            pd(i);
            if(L<=mid)
            {
                up(x,L,R,i<<1,l,mid);
            }
            if(R>mid)
            {
                up(x,L,R,i<<1|1,mid+1,r);
            }
            pu(i);
        }
    }
    int qur(int L,int R,int i,int l,int r)
    {
        if(L<=l&&r<=R)
        {
            return gd[i];
        }
        else
        {
            int mid=(l+r)>>1,ans=0;
            pd(i);
            if(L<=mid)
            {
                ans=gcd(ans,qur(L,R,i<<1,l,mid));
            }
            if(R>mid)
            {
                ans=gcd(ans,qur(L,R,i<<1|1,mid+1,r));
            }
            return ans;
        }
    }
    int fnd(int k)
    {
        return *(st.lower_bound(k));
    }
    void addBlock(int l,int r)
    {
        up(0,l,r,1,1,n);
        up(r-l+1,r,r,1,1,n);
        st.insert(r);
    }
    void delBlock(int l,int r)
    {
        up(0,l,r,1,1,n);
        st.erase(r);
    }
    void deal(int k)
    {
        int u=fnd(k);
        if(k-1>=1)
        {
            int v=fnd(k-1);
            if(u==v)
            {
                if(a[k-1]>a[k])
                {
                    int ln=qur(u,u,1,1,n);
                    delBlock(u-ln+1,u);
                    addBlock(u-ln+1,k-1);
                    addBlock(k,u);
                }
            }
            else
            {
                if(a[k-1]<=a[k])
                {
                    int lnv=qur(v,v,1,1,n);
                    int lnu=qur(u,u,1,1,n);
                    delBlock(v-lnv+1,v);
                    delBlock(u-lnu+1,u);
                    addBlock(v-lnv+1,u);
                }
            }
        }
        if(k+1<=n)
        {
            int v=fnd(k+1);
            if(u==v)
            {
                if(a[k]>a[k+1])
                {
                    int ln=qur(u,u,1,1,n);
                    delBlock(u-ln+1,u);
                    addBlock(u-ln+1,k);
                    addBlock(k+1,u);
                }
            }
            else
            {
                if(a[k]<=a[k+1])
                {
                    int lnu=qur(u,u,1,1,n);
                    int lnv=qur(v,v,1,1,n);
                    delBlock(u-lnu+1,u);
                    delBlock(v-lnv+1,v);
                    addBlock(u-lnu+1,v);
                }
            }
        }
    }
    int tqur()
    {
        if(n==1)
        {
            return 1;
        }
        int ans=qur(1,n-1,1,1,n);
        if(ans==0)
        {
            return n;
        }
        return ys[ans];
    }
    void init()
    {
        for(int i=1;i<=n;i++)
        {
            a[i]=0;
        }
        st.clear();
        addBlock(1,n);
    }
}sg;
void solve()
{
    scanf("%lld%lld",&n,&q);
    sg.init();
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sg.deal(i);
    }
    printf("%lld\n",sg.tqur());
    while(q--)
    {
        int k,x;
        scanf("%lld%lld",&k,&x);
        a[k]=x;
        sg.deal(k);
        int ans=sg.tqur();
        printf("%lld\n",ans);
    }
}
signed main()
{
    pre();
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}