#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using i64=long long;
#define int ll
const int N=2e5+10,mod=1e9+7;
ll qpow(ll a,ll b,ll p){ll res=1;for(;b;b>>=1,a=a*a%p)if(b&1)res=res*a%p;return res;}
int n,m;
int a[N];
int ans[N];
int sum[N];
struct node{
    int l,r;
    int d;
}tr[N*4];

void pushup(node &u,node l,node r){
    u.d=__gcd(l.d,r.d);
}

void pushup(int u){
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r){
    tr[u].l=l,tr[u].r=r;
    tr[u].d=0;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}

void modify(int u,int x){
    if(tr[u].l==tr[u].r){
        tr[u].d=ans[tr[u].l];
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid) modify(u<<1,x);
    else modify(u<<1|1,x);
    pushup(u);
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],ans[i]=0;
    build(1,1,n);
    for(int i=1;i<n;i++){
        if(a[i]>a[i+1]) ans[i]=i;
    }
    if(n==1){
        cout<<1<<"\n";
    }else{
        for(int i=1;i<=n;i++) modify(1,i);
        int w=tr[1].d;
        if(w==0) w=n;
        cout<<sum[tr[1].d]<<"\n";
    }
    for(int i=1,x,v;i<=m;i++){
        cin>>x>>v;
        a[x]=v;
        if(n==1){
            cout<<1<<"\n";
            continue;
        }
        if(x!=n&&a[x]>a[x+1]) ans[x]=x;
        else ans[x]=0;
        if(x!=1&&a[x-1]>a[x]) ans[x-1]=x-1;
        else ans[x-1]=0;
        modify(1,x);
        if(x!=1) modify(1,x-1);
        int w=tr[1].d;
        if(w==0) w=n;
        cout<<sum[w]<<"\n";
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    for(int i=1;i<=200000;i++){
        for(int j=i;j<=200000;j+=i){
            sum[j]++;
        }
    }
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}