#include <bits/stdc++.h>

using namespace std;

template<class F, class S>
ostream &operator<<(ostream &s, const pair<F, S> &v) {
	s << "(" << v.first << ", " << v.second << ")";
	return s;
}
template<ranges::range T> requires (!is_convertible_v<T, string_view>)
istream &operator>>(istream &s, T &&v) { 
	for (auto &&x : v) s >> x; 
	return s; 
}
template<ranges::range T> requires (!is_convertible_v<T, string_view>)
ostream &operator<<(ostream &s, T &&v) { 
	for (auto &&x : v) s << x << ' '; 
	return s; 
}

#ifdef LOCAL
template<class... T> void dbg(T... x) {
	char e{};
	((cerr << e << x, e = ' '), ...);
}
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second

template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
bool chmin(auto &a, auto b) { return (b < a and (a = b, true)); }
bool chmax(auto &a, auto b) { return (a < b and (a = b, true)); }

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;

constexpr i64 mod = 998244353;

vector<int> primes, minp;
vector<int> cntf;
vector<int> mu, phi;
vector<bool> isp;
void Sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    isp.assign(n + 1, 0);
    mu.resize(n + 1);
    phi.resize(n + 1);
    mu[1] = 1;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            isp[i] = 1;
            primes.push_back(i);
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for (i64 p : primes) {
            if (p * i > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                phi[p * i] = phi[i] * p;
                break;
            }
            phi[p * i] = phi[i] * (p - 1);
            mu[p * i] = mu[p] * mu[i];
        }
    }
	cntf.resize(n + 1);
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j += i) {
			cntf[j] += 1;
		}
}
    
void solve() {
	int n, q;
	cin >> n >> q;

	vector<int> A(n);
	cin >> A;

	int cnt = 0, one = 0;
	int cur = 1;
	vector M(n + 1, multiset<int>{});

	auto add = [&](int x) -> void {
		cnt++;
		if (x == 1) {
			one++;
		}
		while (x != 1) {
			int p = minp[x];
			int c = 1;
			while (x % p == 0) {
				x /= p;
				c *= p;
			}
			if (M[p].size()) {
				cur /= *M[p].begin();
			}
			M[p].insert(c);
			cur *= *M[p].begin();
		}
	};

	auto del = [&](int x) -> void {
		cnt--;
		if (x == 1) {
			one--;
		}
		while (x != 1) {
			int p = minp[x];
			int c = 1;
			while (x % p == 0) {
				x /= p;
				c *= p;
			}
			if (M[p].size()) {
				cur /= *M[p].begin();
			}
			M[p].extract(c);
			cur *= *M[p].begin();
		}
	};

	for (int i = 0; i + 1 < n; i++) {
		if (A[i] > A[i + 1]) {
			add(i + 1);
		}
	}

	auto Answer = [&]() -> int {
		if (cnt == 0) {
			return n;
		}
		if (one) {
			return 1;
		}
		return cntf[cur];
	};

	cout << Answer() << '\n';
	while (q--) {
		int p, x;
		cin >> p >> x;
		p--;
		if (p >= 1 and A[p - 1] > A[p]) {
			del(p);
		}
		if (p + 1 < n and A[p] > A[p + 1]) {
			del(p + 1);
		}
		A[p] = x;
		if (p >= 1 and A[p - 1] > A[p]) {
			add(p);
		}
		if (p + 1 < n and A[p] > A[p + 1]) {
			add(p + 1);
		}
		cout << Answer() << '\n';
	}

}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	const int N = 2E5;
	Sieve(N);

	int t = 1;
	cin >> t;

	while (t--) {
		solve();
	}

	return 0;
}