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

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

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

void build(int u, int l, int r)
{
	tr[u].l = l, tr[u].r = r, tr[u].g = 0;
	if (l == r)
		return;
	int m = (l + r) >> 1;
	build(u << 1, l, m);
	build(u << 1 | 1, m + 1, r);
}

void update(int u, int x, int v)
{
	if (tr[u].l == tr[u].r)
	{
		tr[u].g = v;
		return;
	}
	if (x <= tr[u << 1].r)update(u << 1, x, v);
	else update(u << 1 | 1, x, v);
	push_up(u);
}

void solve()
{
	int q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i < n; i++)
		if (a[i] > a[i + 1])update(1, i, i);
	cout << num[tr[1].g] << '\n';
	while (q--)
	{
		int p, v;
		cin >> p >> v;
		if (p > 1)
		{
			if (a[p] < a[p - 1] && v >= a[p - 1])
				update(1, p - 1, 0);
			if (a[p] >= a[p - 1] && v < a[p - 1])
				update(1, p - 1, p - 1);
		}
		if (p < n)
		{
			if (a[p] > a[p + 1] && v <= a[p + 1])
				update(1, p, 0);
			if (a[p] <= a[p + 1] && v > a[p + 1])
				update(1, p, p);
		}
		a[p] = v;
		num[0] = n;
		cout << num[tr[1].g] << '\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;
}