#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,maxval=2147483647;
int tr[4*maxn];
bool tg[maxn];
int cor[maxn];
int gcd(int x,int y){
	if(x%y==0) return y;
	else return gcd(y,x%y);
}
void pushup(int x){
	if(tr[x*2]&&tr[x*2+1]){
		tr[x]=gcd(tr[x*2],tr[x*2+1]);
	}
	else{
		if(tr[x*2]){
			tr[x]=tr[x*2];
		}
		else if(tr[x*2+1]){
			tr[x]=tr[x*2+1];
		}
		else{
			tr[x]=0;
		}
	}
	//cout<<"Pushing up at["<<x<<"]:"<<tr[x*2]<<" and "<<tr[x*2+1]<<" makes "<<tr[x]<<endl;
	return ;
}
void maketree(int x,int l,int r){
	tr[x]=0;
	if(l==r){
		if(tg[l]){
			//cout<<"Marking BreakPoint "<<l<<endl;
			tr[x]=l;
		}
		cor[l]=x;
		return ;
	}
	int mid=(l+r)/2;
	maketree(x*2,l,mid);
	maketree(x*2+1,mid+1,r);
	pushup(x);
	return ;
}
void setBreakPoint(int x){
	//cout<<"Setting BreakPoint at "<<x<<" at subtree "<<cor[x]<<endl;
	tg[x]=1;
	tr[cor[x]]=x;
	x=cor[x];
	while(x>1){
		x>>=1;
		pushup(x);
	}
	return ;
}
void cancelBreakPoint(int x){
	//cout<<"Canceling BreakPoint at "<<x<<" at subtree "<<cor[x]<<endl;
	tg[x]=0;
	tr[cor[x]]=0;
	x=cor[x];
	while(x>1){
		x>>=1;
		pushup(x);
	}
}
int a[maxn];
int cnt[maxn];
void init(int x){
	for(int i=1;i<=x;i++){
		cnt[i]=0;
		for(int j=1;j<=sqrt(i);j++){
			if(i%j==0){
				if(j*j!=i){
					cnt[i]+=2;
				}
				else cnt[i]++;
			}
		}
	}
	return ;
}
int main(){
	init(200000);
	/*for(int i=1;i<=10;i++){
		cout<<cnt[i]<<" ";
	}
	cout<<endl;*/
	int t,n,m,x,y;
	cin>>t;
	while(t--){
		cin>>n>>m;
		a[0]=-1,a[n+1]=maxval;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]<a[i-1]){
				tg[i-1]=1;
			}
			else tg[i-1]=0;
		}
		maketree(1,1,n);
		if(tr[1]==0){
			cout<<n<<endl;
		}
		else cout<<cnt[tr[1]]<<endl;//
		for(int i=1;i<=m;i++){
			cin>>x;
			cin>>a[x];
			if(tg[x-1]){
				if(a[x]>=a[x-1]){
					cancelBreakPoint(x-1);
				}
			}
			else if(tg[x]){
				if(a[x+1]>=a[x]){
					cancelBreakPoint(x);
				}
			}
			else{
				if(a[x]<a[x-1]){
					setBreakPoint(x-1);
				}
				if(a[x]>a[x+1]){
					setBreakPoint(x);
				}
			}
			if(tr[1]==0){
				cout<<n<<endl;
			}
			else cout<<cnt[tr[1]]<<endl;
		}
	}
	return 0;
}