#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int cnt[N];
ll n, m;
struct node {
	int l, r, val;
}tr[N*4];
void build(int root, int l, int r) { //建树
	tr[root].l = l; tr[root].r = r; tr[root].val = 0;
	if (l != r) {
		int mid = (l + r) / 2;
		build(root * 2, l, mid);
		build(root * 2+1, mid+1,r);
	}
}
int gcd(int a, int b) {
	if (b == 0)return a;
	else return gcd(b, a % b);
}
void update(int o,int x,int v) {
	if (tr[o].l == tr[o].r) { tr[o].val = v;
	return; }
	int mid = (tr[o].l + tr[o].r) / 2;
	if(x<=mid)update(o * 2,x, v);
	else update(o * 2+1,x, v);
	tr[o].val = gcd(tr[o * 2].val, tr[o * 2 + 1].val);
	//cout << o * 2 << " " << tr[o * 2].l << " " << tr[o * 2].r << " " << tr[o * 2].val << endl;
	//cout << o * 2 + 1 << " " << tr[o * 2 + 1].l << " " << tr[o * 2 + 1].r << " " << tr[o * 2 + 1].val << endl;
	//cout << o << " " << tr[o].l << " " << tr[o].r << " " << tr[o].val << endl;
}
void solve() {
	cin >> n >> m;
	build(1, 1, n);
	vector<ll>a(n+5);
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (ll i = 1; i < n; i++) {
		if (a[i] > a[i + 1])update(1, i, i);
	}
	if (tr[1].val == 0)cout << n << endl;
	else cout << cnt[tr[1].val] << endl;
	while (m--) {
		ll ii, jj; cin >> ii >> jj;
		 a[ii] = jj;
		if (a[ii - 1] > a[ii])update(1, ii - 1, ii - 1);
		else update(1, ii - 1, 0);
		if (ii + 1 <= n) {
			if (a[ii] > a[ii + 1])update(1, ii, ii);
			else update(1, ii, 0);
		}
		if (tr[1].val == 0)cout << n << endl;
		else cout << cnt[tr[1].val] << endl;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	for (int i = 1; i <= 10000; i++)
	{	for (int j = 1; j * i <= 10000; j++)
		{
		if (i * j < N)cnt[i * j] ++;  //预处理数的因数个数
		else break;
	    }
    }
    int t; cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}