#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];
const ll inf = 3e10;
ll gd[N<<2];
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];
        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);
        }
    }
  //  db(s.size());
    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;
    };
   // db(gd[1]);
   a[0] = inf;
	cout<<(gd[1]==0?n:ok(gd[1]))<<"\n";
    for(int i=1;i<=q;i++){
    	ll id,v;cin>>id>>v;
        a[id] =v;
        auto cal = [&](int p){
        	//cout<<"[i,p]"<<i<<" "<<p<<"\n";
            if(s.count(p)){
                // //原来是,现在不是,那么就要更改
              //  cout<<"i = "<<i<<" ";
                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);
                }   
            }
           // cout<<"s.size()"<<s.size()<<"\n";
        };
    //    cout<<"s.size()"<<s.size()<<"\n";
        cal(id);if(id+1<=n)cal(id+1);
       cout<<(gd[1]==0?n:ok(gd[1]))<<"\n";
    }
}
int main()
{
 	IOS;
    int _;cin>>_;
    while(_--)solve();
}