#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200000;
struct node
{
	int l, r;
	int ll, rr;
	int lz, lz1, lz2;
	int g;
} tr[(N + 10) << 2];
int n, a[N + 10], ll[N + 10], rr[N + 10], num[N + 10];

inline void push_up(int u)
{
	tr[u].g = __gcd(tr[u << 1].g, tr[u << 1 | 1].g);
}

inline void push_down(int u)
{
	if (tr[u].lz)
	{
		tr[u << 1].g = tr[u].lz;
		tr[u << 1].lz = tr[u].lz;
		tr[u << 1 | 1].g = tr[u].lz;
		tr[u << 1 | 1].lz = tr[u].lz;
		tr[u].lz = 0;
	}
	if (tr[u].lz1)
	{
		if (tr[u << 1].l == tr[u << 1].r)tr[u << 1].ll = tr[u].lz1;
		else tr[u << 1].lz1 = tr[u].lz1;
		if (tr[u << 1 | 1].l == tr[u << 1 | 1].r)tr[u << 1 | 1].ll = tr[u].lz1;
		else tr[u << 1 | 1].lz1 = tr[u].lz1;
		tr[u].lz1 = 0;
	}
	if (tr[u].lz2)
	{
		if (tr[u << 1].l == tr[u << 1].r)tr[u << 1].rr = tr[u].lz2;
		else tr[u << 1].lz2 = tr[u].lz2;
		if (tr[u << 1 | 1].l == tr[u << 1 | 1].r)tr[u << 1 | 1].rr = tr[u].lz2;
		else tr[u << 1 | 1].lz2 = tr[u].lz2;
		tr[u].lz2 = 0;
	}
}

void build(int u, int l, int r)
{
	tr[u].l = l, tr[u].r = r, tr[u].lz1 = 0, tr[u].lz2 = 0, tr[u].lz = 0;
	if (l == r)
	{
		tr[u].ll = ll[l];
		tr[u].rr = rr[l];
		tr[u].g = tr[u].rr - tr[u].ll + 1;
		return;
	}
	int m = (l + r) >> 1;
	build(u << 1, l, m);
	build(u << 1 | 1, m + 1, r);
	push_up(u);
}

int query(int u, int l, int r)
{
	if (tr[u].l >= l && tr[u].r <= r)
		return tr[u].g;
	push_down(u);
	int resl = 0, resr = 0;
	if (l <= tr[u << 1].r)resl = query(u << 1, l, r);
	if (r >= tr[u << 1 | 1].l)resr = query(u << 1 | 1, l, r);
	push_up(u);
	if (resl && resr)return __gcd(resl, resr);
	else if (resl)return resl;
	else return resr;
}

int queryll(int u, int x)
{
	if (tr[u].l == tr[u].r)
		return tr[u].ll;
	push_down(u);
	if (x <= tr[u << 1].r)return queryll(u << 1, x);
	else return queryll(u << 1 | 1, x);
	push_up(u);
}

int queryrr(int u, int x)
{
	if (tr[u].l == tr[u].r)
		return tr[u].rr;
	push_down(u);
	if (x <= tr[u << 1].r)return queryrr(u << 1, x);
	else return queryrr(u << 1 | 1, x);
	push_up(u);
}

void update1(int u, int l, int r, int v)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].g += tr[u].ll - v;
		if (l == r)tr[u].ll = v;
		else tr[u].lz1 = v;
		return;
	}
	push_down(u);
	if (l <= tr[u << 1].r)update1(u << 1, l, r, v);
	if (r >= tr[u << 1 | 1].l)update1(u << 1 | 1, l, r, v);
	push_up(u);
}

void update2(int u, int l, int r, int v)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].g += v - tr[u].rr;
		if (l == r)tr[u].rr = v;
		else tr[u].lz2 = v;
		return;
	}
	push_down(u);
	if (l <= tr[u << 1].r)update2(u << 1, l, r, v);
	if (r >= tr[u << 1 | 1].l)update2(u << 1 | 1, l, r, v);
	push_up(u);
}

void update3(int u, int l, int r, int v)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].g = v;
		tr[u].lz = v;
		return;
	}
	push_down(u);
	if (l <= tr[u << 1].r)update3(u << 1, l, r, v);
	if (r >= tr[u << 1 | 1].l)update3(u << 1 | 1, l, r, v);
	push_up(u);
}

int getans()
{
	int r = queryll(1, n) - 1;
	if(r==0)return n;
	int g = query(1, 1, r);
	return num[g];
}

void link(int x, int y)
{
	int lx = queryll(1, x), rx = queryrr(1, x);
	int ly = queryll(1, y), ry = queryrr(1, y);
	update2(1, lx, rx, ry);
	update1(1, ly, ry, lx);
	update3(1, lx, ry, ry - lx + 1);
}

void unlink(int x, int y)
{
	int lx = queryll(1, x), rx = queryrr(1, x);
	int ly = queryll(1, y), ry = queryrr(1, y);
	update2(1, lx, rx, x);
	update1(1, ly, ry, y);
	update3(1, lx, rx, x - lx + 1);
	update3(1, ly, ry, ry - y + 1);
}

void solve()
{
	int q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	ll[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		ll[i] = ll[i - 1];
		if (a[i] < a[i - 1])
			ll[i] = i;
	}
	rr[n] = n;
	for (int i = n - 1; i > 0; i--)
	{
		rr[i] = rr[i + 1];
		if (a[i] > a[i + 1])
			rr[i] = i;
	}
	build(1, 1, n);
	cout << getans() << '\n';
	while (q--)
	{
		int p, v;
		cin >> p >> v;
		if (p > 1)
		{
			if (a[p] < a[p - 1] && v >= a[p - 1])
				link(p - 1, p);
			if (a[p] >= a[p - 1] && v < a[p - 1])
				unlink(p - 1, p);
		}
		if (p < n)
		{
			if (a[p] > a[p + 1] && v <= a[p + 1])
				link(p, p + 1);
			if (a[p] <= a[p + 1] && v > a[p + 1])
				unlink(p, p + 1);
		}
		a[p] = v;
		cout << getans() << '\n';
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for (int i = 1; i <= N; i++)
		for (int j = i; j <= N; j += i)
			num[j]++;
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}