#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stdio.h>
#include<stack>
#include<list>
using namespace std;
#define ffp(x,y,z) for(ll (x) = (y);(x)<=(z);(x++))
#define ffs(x,y,z) for(ll (x) = (y);(x)>=(z);(x--))
#define pii pair<ll ,ll> 
#define ll long long int
#define endl '\n'
#define q_ (qd())
#define lon(x) (R[x]-L[x]+1)
const double ex = 1e-7;
const int iINF = 0x3f3f3f3f;
const ll lINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 998244353;
long long int qd() {
	long long w = 1, c, ret;
	while ((c = getchar()) > '9' || c < '0')
		w = (c == '-' ? -1 : 1); ret = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		ret = ret * 10 + c - '0';
	return ret * w;
}
ll qs(ll a, ll b)
{
	ll bei = a;
	a = 1;
	while (b)
	{
		if (b & 1) { a = a * bei % MOD; }
		bei = bei * bei % MOD;
		b >>= 1;
	}
	return a;
}
ll inv(ll a)
{
	return qs(a, MOD - 2);
}
static ll Max(ll a1 = -lINF, ll a2 = -lINF, ll a3 = -lINF, ll a4 = -lINF, ll a5 = -lINF)
{
	return max(max(max(max(a1, a2), a3), a4), a5);
}
static ll Min(ll a1 = lINF, ll a2 = lINF, ll a3 = lINF, ll a4 = lINF, ll a5 = lINF)
{
	return min(min(min(min(a1, a2), a3), a4), a5);
}

ll tr[200200 << 2];//值是gcd
int L[200200 << 2];//规定1为正
int R[200200 << 2];
int ml[200200 << 2];//区间左边，向右
int mr[200200 << 2];//区间右边，向左有多少个正号
ll num[200200];

ll gcd(ll a, ll b) {
	if (a % b == 0)
		return b;
	else
		return (gcd(b, a % b));
}

void updata(int now)
{
	//两个子树都是空的
	if (ml[now * 2] == lon(now * 2) && ml[now * 2 + 1] == lon(now * 2 + 1))
	{
		if (tr[now * 2] && tr[now * 2 + 1]) { tr[now] = gcd(tr[now * 2], tr[now * 2 + 1]); }
		else if (tr[now * 2] || tr[now * 2 + 1]) { tr[now] = tr[now * 2] + tr[now * 2 + 1]; }
		else tr[now] = 0;
		mr[now] = ml[now] = lon(now);
	}
	//左边没点,右边有点
	if (ml[now * 2] == lon(now * 2) && ml[now * 2 + 1] != lon(now * 2 + 1))
	{
		if (tr[now * 2] && tr[now * 2 + 1]) { tr[now] = gcd(tr[now * 2], tr[now * 2 + 1]); }
		else if (tr[now * 2] || tr[now * 2 + 1]) { tr[now] = tr[now * 2] + tr[now * 2 + 1]; }
		else tr[now] = 0;
		mr[now] = mr[now * 2 + 1];
		ml[now] = lon(now*2) + ml[now * 2 + 1];
	}
	//左边有点,右边没点
	if (ml[now * 2] != lon(now * 2) && ml[now * 2 + 1] == lon(now * 2 + 1))
	{
		if (tr[now * 2] && tr[now * 2 + 1]) { tr[now] = gcd(tr[now * 2], tr[now * 2 + 1]); }
		else if (tr[now * 2] || tr[now * 2 + 1]) { tr[now] = tr[now * 2] + tr[now * 2 + 1]; }
		else tr[now] = 0;

		ml[now] = ml[now * 2];
		mr[now] = mr[now * 2] + lon(now * 2 + 1);
	}
	//两边都有点
	if (ml[now * 2] != lon(now * 2) && ml[now * 2 + 1] != lon(now * 2 + 1))
	{
		mr[now] = mr[now * 2 + 1];
		ml[now] = ml[now * 2];
		tr[now] = mr[now * 2] + ml[now * 2 + 1]+1;
		if (tr[now * 2]) { tr[now] = gcd(tr[now], tr[now * 2]); }
		if (tr[now * 2 + 1]) { tr[now] = gcd(tr[now], tr[now * 2 + 1]); }
	}
	if (now == 1)
	{
		//tr[now] = gcd(tr[now * 2], tr[now * 2 + 1]);
		if (tr[now])
		{
			tr[now] = gcd(tr[now], ml[now]);
		}
		else
		{
			tr[now] = ml[now];
		}
	}
}

void bud(int now, int l, int r)
{//规定1为正

	L[now] = l;
	R[now] = r;

	if (l == r)
	{
		if (num[l-1] <= num[l])
		{//当前是
			ml[now] = mr[now] = 1;
		}
		else
		{
			ml[now] = mr[now] = 0;
		}
		return;
	}

	int med = (l + r) >> 1;
	bud(now * 2, l, med);
	bud(now * 2 + 1, med + 1, r);
	updata(now);
}
void ask(int now,int l,int r,int p,ll v)
{
	if (l == r) 
	{
		num[l] = v;
		if (num[l - 1] <= num[l])
		{//当前是
			ml[now] = mr[now] = 1;
		}
		else
		{
			ml[now] = 0;
			mr[now] = 0;
		}
		return;
	}
	int med = (l + r) >> 1;
	if (p <= med)ask(now * 2, l, med, p, v);
	if (p > med)ask(now * 2 + 1, med + 1, r, p, v);
	updata(now);
}

ll getans(ll x)
{
	ll k = 0;
	for (ll i = 1; i * i <= x; i++)
	{
		if (x % i == 0)
		{
			if (x / i != i) { k += 2; }
			else { k += 1; }
		}
	}
	return k;
}

int main()
{
	int t = q_;
	while (t--)
	{
		ll n = q_;
		ll q = q_;
		ffp(i, 1, n)
		{
			num[i] = q_;
		}
		bud(1, 1, n);
		num[0] = 0;
		if (tr[1] && tr[1]!= n)
		{
			cout << getans(tr[1]) << endl;
		}
		else { cout << n << endl; }
		ffp(i, 1, q)
		{
			ll p = q_;
			ll v = q_;
			ask(1, 1, n, p, v);
			if (p != n) 
			{ ask(1, 1, n, p + 1, num[p + 1]); }

			if (tr[1] && tr[1]!=n)
			{
				cout << getans(tr[1]) << endl;
			}
			else { cout << n << endl; }
		}
	}
	
	return 0;
}