#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
inline int read(){
	register int x=0,f=0;
	register char c=getchar();
	while(c>'9'||c<'0')f|=(c=='-'),c=getchar();
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}return f?(-x):x;
}
int T,a[200001],n,q,ans,c[200001],cha[200001];
vector<int>ys[200001];
inline void add(int x,int y){for(;x<=n;x+=(x&(-x)))c[x]+=y;}
inline int ask(int x){int fh=0;for(;x;x-=(x&(-x)))fh+=c[x];return fh;}
inline void check(){
	ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=(n/i);j++)if(ask(j*i)-ask((j-1)*i+1))cha[i]++;
		ans+=(cha[i]==0);
	}
}
inline void ad(int x){
	add(x,1);
	for(auto v:ys[x]){
		if(ask(x)-ask(x-v+1))cha[v]++;
		if(cha[v]==1)ans--;
	}
}
inline void de(int x){
	add(x,-1);
	for(auto v:ys[x]){
		if(ask(x)-ask(x-v+1)==0)cha[v]--;
		if(cha[v]==0)ans++;
	}
}
int main(){
	//freopen("11.in","r",stdin);
	//freopen("11.out","w",stdout);
	for(ll i=1;i<=200000;i++){
		ys[i].push_back(i);
		for(ll j=i;i*j<=200000;j++)ys[j*i].push_back(i);
	}
	T=read();
	while(T--){
		n=read(),q=read();
		for(int i=1;i<=n;i++)c[i]=cha[i]=0;
		for(int i=1;i<=n;i++){
			a[i]=read();
			if(a[i]<a[i-1])add(i,1);
		}check();
		printf("%d\n",ans);
		for(int i=1;i<=q;i++){
			int p=read(),v=read();
			if(p!=1){
				if(a[p]>=a[p-1]&&v<a[p-1])ad(p);
				else if(a[p]<a[p-1]&&v>=a[p-1])de(p);
			}
			if(p!=n){
				if(a[p]<=a[p+1]&&v>a[p+1])ad(p+1);
				else if(a[p]>a[p+1]&&v<=a[p+1])de(p+1);
			}
			a[p]=v;printf("%d\n",ans);
		}
	}
	return 0;
}