#include<bits/stdc++.h>
#include<numeric>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define epb emplace_back
#define endl
#define SZ(X) (int)((X).size())
template<typename T>T mabs(T x){return x>=0?x:-x;}
const int N=1.1e6,mod=998244353;
int a[N],n;
struct trar{
	ll tree[N];
	#define lb(i) ((i)&-(i))
	void _add(int i,ll x){
		for(;i<=n;i+=lb(i))tree[i]+=x;
	}
	ll _sum(int r){
		assert(r>0);
		ll res=0;
		for(;r>0;r^=lb(r))res+=tree[r];
		return res;
	}
	ll query(int i){
		return _sum(i);
	}
	void modify(int l,int r,ll x){
		assert(l<=r);
		ll adt=x;//-query(l);
		_add(l,adt);
		_add(r+1,-adt);
	}
}L,R;
int ss[N];
void work(){
	int q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	int sq=sqrt(n+1);
	map<int,int>bl;
	auto era=[&](int x){
		//cerr<<"ERA"<<x<<"#\n";
		assert(bl[x]>0);
		if(bl[x]>1)bl[x]--;
		else if(bl[x]==1)bl.erase(x);
	};
	auto getans=[&](){
		if(bl.size()<=sq){
			if(bl.size()==0)return n;
			int res=bl.begin()->fs;
			for(auto e:bl)res=gcd(res,e.fs);
			return ss[res];
		}
		else return 1;
	};
	
	int las=1;
	for(int i=2;i<=n+1;i++){
		if(a[i]<a[i-1]){
			int l=las,r=i-1;
			L.modify(l,r,l);
			R.modify(l,r,r);
			if(r<n)bl[r-l+1]++;
			las=i;
		}
	}
	cout<<getans()<<"\n";
	
	for(int i=1;i<=n;i++)
		cerr<<'('<<L.query(i)<<','<<R.query(i)<<")";cerr<<"\n";
	for(auto e:bl)
		cerr<<'('<<e.fs<<','<<e.sc<<")";cerr<<"\n";

	
	a[0]=2e9+1;
	for(int j=1;j<=q;j++){
		int i,x;
		scanf("%d%d",&i,&x);
		set<pii>tmp;
		for(int k=max(i-1,1);k<=min(i+1,n);k++)
			tmp.insert(pii(L.query(k),R.query(k)));
		for(auto e:tmp){
			if(e.sc<n)era(e.sc-e.fs+1);
		}
		//cerr<<"$";
		
		a[i]=x;
		vector<pii>temp;
		auto update=[&](int l,int r){
			//cerr<<"up#"<<l<<" "<<r<<"\n";//
			temp.pb(pii(l,r));
		};
		int l,r;
		if(a[i-1]<=x&&x<=a[i+1]){
			l=L.query(i-1),r=R.query(i+1);
			update(l,r);
		}
		else if(a[i-1]<=x){
			l=L.query(i-1),r=i;
			update(l,r);
			if(i<n){
				l=i+1,r=R.query(i+1);
				update(l,r);
			}
		}
		else if(x<=a[i+1]){
			l=i,r=R.query(i+1);
			update(l,r);
			if(i>1){
				l=L.query(i-1),r=i-1;
				update(l,r);
			}
		}
		else{
			if(i<n){
				l=i+1,r=R.query(i+1);
				update(l,r);
			}
			if(i>1){
				l=L.query(i-1),r=i-1;
				update(l,r);
			}
			update(i,i);
		}
		for(auto e:tmp)
			L.modify(e.fs,e.sc,-e.fs),R.modify(e.fs,e.sc,-e.sc);
		
		for(int i=1;i<=n;i++)
			cerr<<'('<<L.query(i)<<",_"<<R.query(i)<<")";cerr<<"\n";
		
		
		for(auto e:temp){
			l=e.fs,r=e.sc;
			L.modify(l,r,l),R.modify(l,r,r);
			if(r<n)bl[r-l+1]++;
		}
			
		cout<<getans()<<"\n";
		
		////
		for(int i=1;i<=n;i++)
			cerr<<'('<<L.query(i)<<','<<R.query(i)<<")";cerr<<"\n";
		for(auto e:bl)
			cerr<<'('<<e.fs<<';'<<e.sc<<")";cerr<<"\n";
	}
}
int main(){
	for(int i=1;i<=2e5;i++){
		for(int j=1;j*j<=i;j++){
			if(i%j==0)ss[i]+=1+(j!=i/j);
		}
	}
	int t;
	scanf("%d",&t);
	while(t--)work();
	return 0;
}