#include <bits/stdc++.h>
#define db(x) cerr<<#x<<(x)<<"\n"
#define db1(x) cerr<<#x<<(x)<<" "
#define ll long long 
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int Mod = 1e9+7;
const int N = 2.1e5;
int n,m,q;
ll a[N],w[N],pos[N];
const ll inf = 3e10;
ll gd[N<<2];
bool ins[N];
void pushup(int o){
    gd[o] = __gcd(gd[o<<1],gd[o<<1|1]);
}
void build(int o,int l,int r){
    if(l==r){
        gd[o] =w[l];
        pos[l] =o;
        return ;
    }
    int mid = (l+r)>>1;
    build (o<<1,l,mid);
    build (o<<1|1,mid+1,r);
    pushup(o);
}
void upd(int o,int l,int r,int pos,int v){
    if(pos<l||pos>r)return;
    if(l==pos){
        gd[o] = v;
        return ;
    }
    int mid = (l+r)>>1;
    if(pos<=mid)upd(o<<1,l,mid,pos,v);
    else upd(o<<1|1,mid+1,r,pos,v);
    pushup(o);
}
ll que(int o,int l,int r,int s,int t){
    if(s<=l&&r<=t){
        return gd[o];
    }
    int mid =(l+r)>>1;
    ll gd1 =0,gd2 =0;
    if(s<=mid)gd1 = que(o<<1,l,mid,s,t);
    if(t>mid)gd2 = que(o<<1|1,mid+1,r,s,t);
    ll C = __gcd(gd1,gd2);
    return C;

}
void solve()
{
    cin>>n>>q;
    set<int> s;
    s.insert(1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        if(a[i]<a[i-1]){
            s.insert(i);
        }
    }
    for(auto it = s.begin();it!=s.end();++it){
        if(*it==1)continue;
        w[*it] = *it-*prev(it);
    }
    s.insert(n+1);//插入哨兵
    build(1,1,n);
    ll nowgd = gd[1]; 
    auto ok=[&](ll x){
        ll ans =0;
        for(ll i=1;i*i<=x;i++){
            if(x%i==0&&i*i!=x)ans+=2;
            else if(x%i==0)ans++;
        }
        return ans;
    };
    int ans = ok(n);
   if(s.size()>2)cout<<ok(nowgd)<<"\n";
   else cout<<ans<<"\n";
    for(int i=1;i<=q;i++){
    	ll id,v;cin>>id>>v;
        a[id] =v;
        auto cal = [&](int p){
            if(s.count(p)){
                // //原来是,现在不是,那么就要更改
                if(a[p]>=a[p-1]){
                    auto le = s.lower_bound(p);--le;
                    auto ri = s.upper_bound(p);
                    int lp = *le,rp = *ri;
                    upd(1,1,n,p,0);
                    upd(1,1,n,rp,rp-lp);//右边第一个的左部分区间改变
                    s.erase(p);//删除该地方
                }
                //原来是，现在也是没有影响
            }else if(!s.count(p)){
                //原来不是，现在不是没有影响，但是现在是就有影响了
                if(a[p]<a[p-1]){ //现在是
                    auto le = s.lower_bound(p);--le;
                    auto ri = s.upper_bound(p);
                    upd(1,1,n,p,p-*le);
                    upd(1,1,n,*ri,*ri-p);
                    s.insert(p);
                }   
            }
        };
        if(id!=1)cal(id);
        if(id+1<=n)cal(id+1);
      //  cout<<gd[1]<<" \n";
     // 	cout<<ok(gd[1])<<"\n";
   //  cout<<"i  = "<<i<<" s.size()= "<<s.size()<<"\n";
       	if(s.size()>2)cout<<ok(gd[1])<<"\n";
       	else cout<<ans<<"\n";
    }
}
int main()
{
 	IOS;
    int _;cin>>_;
    while(_--)solve();
}