#include <bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define ll long long
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;

typedef vector <int> vi;
typedef pair <int, int> pii;

template <typename T> inline void rd(T &x) { x = 0; bool f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = getchar(); f ? x = -x : 0; }
template <typename T> inline void write(T x) { if (x < 0) x = -x, putchar('-'); static short s[20], _ = 0; do s[++_] = x%10, x /= 10; while(x); while (_) putchar(s[_--]|48); }
template <typename T, typename ...Args> inline void rd(T &x, Args&... _){ rd(x); rd(_...); }

const int N = 2e5+5;
int n, q, a[N], g[N], t[N<<2];

void build(int p, int l, int r) {
	if (l == r) {
		if (l < n && a[l] > a[l+1]) t[p] = l;
		return;
	}
	int mid = l+r>>1;
	build(ls, l, mid), build(rs, mid+1, r);
	t[p] = __gcd(t[ls], t[rs]);
}

void modify(int p, int l, int r, int x, int v) {
	if (l == r) return t[p] = v, void();
	int mid = l+r>>1;
	x <= mid ? modify(ls, l, mid, x, v) : modify(rs, mid+1, r, x, v);
	t[p] = __gcd(t[ls], t[rs]);
}

void solve() {
	rd(n, q); g[0] = n;
	for (int i = 1; i <= n; ++i) rd(a[i]);
	build(1, 1, n);
	write(g[t[1]]), enter;
	while (q--) {
		int p, v; rd(p, v); a[p] = v;
		if (1 < p) modify(1, 1, n, p-1, a[p-1] > v ? p-1 : 0);
		if (p < n) modify(1, 1, n, p, v > a[p+1] ? p : 0);
		write(g[t[1]]), enter;
	}
}

int main() {
	for (int i = 1; i < N; ++i)
		for (int j = i; j < N; j += i)
			++g[j];
	int t; rd(t);
	while (t--) solve();
	return 0;
}