#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;i++) 
#define dep(i,l,r) for(int i=r;i>=l;i--) 
const int N=3e5+10;
using pii=array<int,2>;
int gcdv[N*4];
int b[N*4];
int a[N*4];

void build(int o,int l,int r){
	if(l==r){
		gcdv[o]=b[l];
	}
	else{
		int mid=l+r>>1;
		build(o*2,l,mid);
		build(o*2+1,mid+1,r);
		gcdv[o]=__gcd(gcdv[o*2],gcdv[o*2+1]);
	}
} 
void update(int o,int l,int r,int yl,int yr,int v){
	if(yl<=l&&r<=yr){
		gcdv[o]=v;
	}
	else{
		int mid=l+r>>1;
		if(yl<=mid){
			update(o*2,l,mid,yl,yr,v);
		}
		if(mid<yr){
			update(o*2+1,mid+1,r,yl,yr,v);
		}
		gcdv[o]=__gcd(gcdv[o*2],gcdv[o*2+1]);
	}
}
int query(int o,int l,int r,int yl,int yr){
	int ans=0;
	if(yl<=l&&r<=yr){
		ans=__gcd(ans,gcdv[o]);
	}
	else{
		int mid=l+r>>1;
		if(yl<=mid){
			ans=__gcd(ans,query(o*2,l,mid,yl,yr));
		}
		if(mid<yr){
			ans=__gcd(ans,query(o*2+1,mid+1,r,yl,yr));
		}
	}
	return ans;
}
int check(int d){
	int ans=1;
	for(int j=2;j<=d;j++){
		while(d%j==0){
			ans++;
			d/=j;
		}
	}
	return ans;
}
void solve(){
	int n,m;cin>>n>>m;
	int last=-1e9;
	rep(i,1,n){
		cin>>a[i];
		if(a[i]<last){
			b[i-1]=i-1;
		}
		else{
			b[i-1]=0;
		}
		last=a[i];
	}
	b[n]=0;
	build(1,1,n);
	cout<<check(query(1,1,n,1,n))<<endl;
	a[n+1]=1e9+10;
	rep(i,1,m){
		int x,v;cin>>x>>v;
		a[x]=v;
		if(a[x-1]<=a[x]&&a[x]<=a[x+1]){
			update(1,1,n,x,x,0);
			update(1,1,n,x-1,x-1,0);
		}
		else if(a[x-1]<=a[x]&&a[x]>a[x+1]){
			update(1,1,n,x,x,x);
			update(1,1,n,x-1,x-1,0);
		}
		else if(a[x-1]>a[x]&&a[x]<=a[x+1]){
			update(1,1,n,x,x,0);
			update(1,1,n,x-1,x-1,x-1);
		}
		else if(a[x-1]>a[x]&&a[x]>a[x+1]){
			update(1,1,n,x,x,x);
			update(1,1,n,x-1,x-1,x-1);
		}
		
		update(1,1,n,n,n,0);
		int d=query(1,1,n,1,n);
		int ans=check(d);
		
		cout<<ans<<endl;
	}
	
}
signed main(){
	int _=1;
	cin>>_;
	while(_--)solve(); 
	return 0;
} 
/*
1
5 2
4 3 2 6 1
2 5
3 5
*/