#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

using ll=long long;

#define f(i, a, b) for (int i = a; i <= b; i++)

template<typename T,auto e,auto op>
struct BIT
{
    vector<T> v,origin;
    int n;
    BIT(const vector<T>& aa,int n):n(n),v(n+1,e()),origin(aa){
    	for(int i=1;i<=n;++i)update(i,origin[i]);
    }
    int lowbit(int x){
    	return (x&(-x));
    }
    void update(int x, T val)
    {
    	origin[x]=val;
        while(x<=n){
            v[x]=origin[x];
            int low=lowbit(x);
            for(int i=1;i<low;i<<=1){
            	v[x]=op(v[x],v[x-i]);
            }
            x+=lowbit(x);
        }
    }
    T query(int l, int r)
    {
    	//for(int i=1;i<=n;++i)cout<<origin[i]<<" \n"[i==n];
        T ans = e();
        while (r >= l)
        {
            ans = op(ans, origin[r]);
            r--;
            while (r - lowbit(r) >= l)
            {
                ans = op(v[r], ans);
                r -= lowbit(r);
            }
        }
        return ans;
    }
};

template<typename T>
T GCD(T x, T y) {return std::gcd(x,y);}

using bit_gcd=BIT<int,[](){return 0;},GCD<int>>;


ll tt,n,q,a[(int)2e5+9],res[(int)2e5+9]; 


void solve(){
	cin>>n>>q;
	f(i,1,n)cin>>a[i];
	vector v(n+1,0);
	for(int i=2;i<=n;++i){
		if(a[i]<a[i-1]){
			v[i-1]=i-1;
		}
	}
	bit_gcd bit(v,n);
	int tmp = bit.query(1,n);
	if (tmp==0)cout<<n<<"\n";
	else cout<<res[tmp]<<"\n";
	for(int i=1;i<=q;++i){
		ll x,v;
		cin>>x>>v;
		a[x]=v;
		if(x>1&&a[x]<a[x-1])bit.update(x-1,x-1);
		else if(x>1)bit.update(x-1,0);
		if(x<n&&a[x]>a[x+1])bit.update(x,x);
		else if(x<n)bit.update(x,0);

		int tmp = bit.query(1,n);
		//cout<<tmp<<"?\n";
		if (tmp==0)cout<<n<<"\n";
		else cout<<res[tmp]<<"\n";
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=int(2e5);++i){
    	for(int j=i;j<=int(2e5);j+=i){
    		res[j]+=1;
    	}
    }


    cin>>tt;
    f(S,1,tt)solve();
    return 0;
}