//Linkwish's code
#include<bits/stdc++.h>
#define endl '\n'
#define si inline
#define fi first
#define se second
using namespace std;typedef long long ll;typedef __int128 li;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;typedef const int ci;
typedef const ll cl;const int iinf=INT_MAX;const ll linf=1e18;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

namespace LinkWish{

	ci N=200005;

	int n,m;
	int a[N],b[N],S;

	int t[N];
	int sum[N];
	vector<int> d[N];

	void modify(int x,int v){
		if(v==b[x])return ;
		for(int i:d[x]){
			t[sum[i]]--;
			sum[i]+=v-b[x];
			t[sum[i]]++;
		}
		S+=v-b[x],b[x]=v;
	}

	si void solve(){
		cin>>n>>m,S=0;
		for(int i=0;i<=n;i++)t[i]=sum[i]=0,d[i].clear();

		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<n;i++)S+=(b[i]=(a[i]>a[i+1]));

		for(int i=1;i<=n;i++){
			for(int j=i;j<n;j+=i){
				d[j].push_back(i);
				sum[i]+=b[j];
			}
			t[sum[i]]++;
		}

		cout<<t[S]<<endl;
		while(m--){
			int x,y;cin>>x>>y;
			a[x]=y;
			if(x<n)modify(x,(a[x]>a[x+1]));
			if(x>1)modify(x-1,(a[x-1]>a[x]));
			cout<<t[S]<<endl;
		}
	}

	void mian(){
		int TT;cin>>TT;
		while(TT--)solve();
	}
}

signed main(){
	#ifndef ONLINE_JUDGE
	assert(freopen("in.in","r",stdin));
	//assert(freopen("out.err","w",stderr));
	assert(freopen("out.out","w",stdout));
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	LinkWish::mian();
	return 0;
}