// Problem: I. Good Partitions
// Contest: Codeforces - 2024 ICPC Asia Chengdu Regional Contest (The 3rd Universal Cup. Stage 15: Chengdu)
// URL: https://codeforces.com/gym/105486/problem/I
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
//#define int long long  
#define ls root<<1
#define rs root<<1|1
using namespace std;
const int N=2e5+10;

struct SegmentTree{
    int l,r,gcd;
    int left,right;
    int tag;
}tree[N<<3];
long long arr[N<<1];
int L[N<<1],R[N<<1],Len[N<<1];
int cnt[N<<1];
int n,m,k,q;

void pushup(int root)
{
    tree[root].gcd=__gcd(tree[ls].gcd,tree[rs].gcd);
   // cout<<tree[root].gcd<<' ';
   // tree[root].left=min(tree[ls].left,tree[rs].left);
   // tree[root].right=max(tree[ls].right,tree[rs].right);
    //if(tree[root].right==n) tree[root].gcd=0;
}

void build(int l,int r,int root)
{
    tree[root].l=l,tree[root].r=r;
    tree[root].gcd=0;
    tree[root].left=0;
    tree[root].right=0;
    tree[root].tag=0;
    if(l==r)
    {
        tree[root].gcd=Len[l];
        tree[root].left=L[l];
        tree[root].right=R[l];
        if(R[l]==n) tree[root].gcd=0;
        tree[root].tag=0;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushup(root);
}

void pushdown(int root)
{
    if(!tree[root].tag) return;
    if(tree[root].right==n) tree[root].gcd=0;
    tree[ls].gcd=tree[root].gcd;
    tree[rs].gcd=tree[root].gcd;
    tree[ls].left=tree[root].left;
    tree[rs].left=tree[root].left;
    tree[ls].right=tree[root].right;
    tree[rs].right=tree[root].right;
    tree[ls].tag=tree[rs].tag=tree[root].tag;
    tree[root].tag=tree[root].left=tree[root].left=0;
}



void Change(int l,int r,int root,int val)
{
    if(tree[root].l>=l&&tree[root].r<=r){
    	//pushdown(root);
        tree[root].gcd=val;
        if(r==n) tree[root].gcd=0;
        tree[root].right=r;
        tree[root].left=l;
        tree[root].tag=1;
        return;
    }
    pushdown(root);
    int mid=tree[root].l+tree[root].r>>1;
    if(l<=mid) Change(l,r,ls,val);
    if(r>mid) Change(l,r,rs,val);
    pushup(root);
    
}

int Search1(int pos,int root,int f)
{
    if(tree[root].l==tree[root].r)
    return (f==0?tree[root].left:tree[root].right);
    pushdown(root);
    int mid=tree[root].l+tree[root].r>>1;
    int kk=0;
    if(pos<=mid) kk=Search1(pos,ls,f);
    if(pos>mid)  kk=Search1(pos,rs,f);
    return kk;
}

int Query(int l,int r,int root)
{
    if(tree[root].l>=l&&tree[root].r<=r){
        return tree[root].gcd;
    }
    pushdown(root);
    int mid=tree[root].l+tree[root].r>>1;
    int ans=0;
    if(l<=mid )ans=__gcd(ans,Query(l,r,ls));
    if(r>mid) ans=__gcd(ans,Query(l,r,rs));
    return ans;
}

void shuchu(int pos)
{
    //cout<<Query(1,n,1)<<' ';
    int k=Query(1,n,1);
    //cout<<k<<' ';
    if(k==0) cout<<n<<'\n';
    else
    cout<<cnt[k]<<'\n';
}

void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>arr[i];
    arr[n+1]=0ll;
    for(int i=1;i<=n;i++)
    {
        int pos=i;
        while(pos+1<=n&&arr[pos]<=arr[pos+1]) pos++;
        int len=pos-i+1;
        for(int j=i;j<=pos;j++)
        Len[j]=(pos==n?0ll:len),L[j]=i,R[j]=pos;
        i=pos;
    }
    build(1,n,1);
    //arr[n+1]=2e9+1;
    //cnt[0]=5;
    //cout<<endl;
    //cout<<tree[1].gcd<<'\n';
    //cout<<Len[1]<<' '<<Len[2]<<' '<<Len[3]<<'\n';
    
    shuchu(1);
    while(q--)
    {
        long long val;
        int pos;
        cin>>pos>>val;
        long long x=arr[pos-1];
        long long y=arr[pos];
        long long z=arr[pos+1];
        //情况1
        if(x>y&&y>z){
            if(x>val&&val>z)
            {
                arr[pos]=val;
                //直接输出
                shuchu(pos);
            }
            if(x>val&&val<=z){
            	if(pos+1<=n){
                int rr=Search1(pos+1,1,1);
                int len=rr-pos+1;
                Change(pos,rr,1,len);
                }
                arr[pos]=val;
                shuchu(pos);
                //
            }
            if(x<=val&&val>z){
            	if(pos-1>=1){
                int ll=Search1(pos-1,1,0);
                int len=pos-ll+1;
                Change(ll,pos,1,len);
                }
                arr[pos]=val;
                shuchu(pos);
            }
            if(x<=val&&val<=z){
                int ll=Search1(pos-1,1,0);
                if(pos-1<=0) ll=1;
                int rr=Search1(pos+1,1,1);
                if(pos+1>n) rr=n;
                int len=rr-ll+1;
                Change(ll,rr,1,len);
                arr[pos]=val;
                shuchu(pos);
            }
        }
        //情况2
        if(x>y&&y<=z)
        {
            if(x>val&&val<=z)
            {
                arr[pos]=val;
                //直接输出
                shuchu(pos);
            }
            if(x>val&&val>z){
            	if(pos+1<=n){
                int rr=Search1(pos+1,1,1);
                int len=rr-pos;
                Change(pos+1,rr,1,len);
                }
                Change(pos,pos,1,1);
                arr[pos]=val;
                shuchu(pos);
                //
            }
            if(x<=val&&val>z){
            	if(pos-1>0){
                int ll=Search1(pos-1,1,0);
                int len=pos-ll+1;
                Change(ll,pos,1,len);}
                if(pos+1<=n){
                int rr=Search1(pos+1,1,1);
                int len=rr-pos;
                Change(pos+1,rr,1,len);
                }
                arr[pos]=val;
                shuchu(pos);
            }
            if(x<=val&&val<=z){
                int ll=Search1(pos-1,1,0);//0表示找左边界
                if(pos-1<=0) ll=1;
                int rr=Search1(pos,1,1);//1表示找右边界
                int len=rr-ll+1;
                Change(ll,rr,1,len);
                arr[pos]=val;
                shuchu(pos);
            }
        }
        //情况3
        
        if(x<=y&&y>z){
            if(x>val&&val>z)
            {
                //直接输出
                int ll=Search1(pos-1,1,0);
                int len=pos-ll;
                //cout<<len<<' ';
                Change(ll,pos-1,1,len);
                Change(pos,pos,1,1);
                arr[pos]=val;
                shuchu(pos);
            }
            if(x>val&&val<=z){
                int ll=Search1(pos-1,1,0);
                int len=pos-ll;
                Change(ll,pos-1,1,len);
                int rr=Search1(pos+1,1,1);
                len=rr-pos+1;
                Change(pos,rr,1,len);
                arr[pos]=val;
                shuchu(pos);
                //
            }
            if(x<=val&&val>z){
                arr[pos]=val;
                shuchu(pos);
            }
            if(x<=val&&val<=z){
                int rr=Search1(pos+1,1,1);
                int ll=Search1(pos-1,1,0);
                int len=rr-ll+1;
                Change(ll,rr,1,len);
                arr[pos]=val;
                shuchu(pos);
            }
        }
        
        //情况4
        if(x<=y&&y<=z){
            if(x>val&&val>z)
            {
                //直接输出
                int ll=Search1(pos-1,1,0);
                int len=pos-ll;
                Change(ll,pos-1,1,len);
                int rr=Search1(pos+1,1,1);
                len=rr-pos;
                Change(pos+1,rr,1,len);
                Change(pos,pos,1,1);
                arr[pos]=val;
                shuchu(pos);
            }
            if(x>val&&val<=z){
                int ll=Search1(pos-1,1,0);
                int len=pos-ll;
                Change(ll,pos-1,1,len);
                int rr=Search1(pos+1,1,1);
                len=rr-pos+1;
                Change(pos,rr,1,len);
                arr[pos]=val;
                shuchu(pos);
                //
            }
            if(x<=val&&val>z){
                int rr=Search1(pos+1,1,1);
                int len=rr-pos;
                Change(pos+1,rr,1,len);
                int ll=Search1(pos,1,0);
                len=pos-ll+1;
                Change(ll,pos,1,len);
                arr[pos]=val;
                shuchu(pos);
            }
            if(x<=val&&val<=z){
                arr[pos]=val;
                shuchu(pos);
            }
        }
        
        
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    for(int i=1;i<N;i++){
        for(int j=1;j<=i/j;j++)
        {
            if(i%j==0){
            	cnt[i]++;
            	if(i/j!=j) cnt[i]++;
            }
        }
    }
    //cout<<cnt[1]<<' ';
    int _=1;
    cin>>_;
    while(_--)
    solve();
    return 0;
}