#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int d[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    d[1] = 1;
    for (int i = 2; i < N; i++) {
        d[i] += 2;
        for (int j = 2 * i; j < N; j += i) {
            d[j]++;
        }
    }
    int tt; cin >> tt;
    while(tt--){
        int n, q;
        cin >> n >> q;
        int t = sqrt(n);
        vector<int> a(n + 1), b(n + 1), L(n + 1), R(n + 1), pos(n + 1), sum(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i < n; i++) {
            if (a[i] > a[i + 1]) b[i] = i;
        }
        for (int i = 1; i <= t; i++) {
            L[i] = 1 + (i - 1) * t;
            R[i] = i * t;
        }
        if (R[t] < n) {
            t++;
            L[t] = 1 + R[t - 1];
            R[t] = n;
        }
        for (int i = 1; i <= t; i++) {
            for (int j = L[i]; j <= R[i] && j <= n; j++) {
                pos[j] = i;
                sum[i] = gcd(sum[i], b[j]);
            }
        }
        auto getans = [&]() ->int {
            int all = 0;
            for (int i = 1; i <= t; i++) {
                all = gcd(all, sum[i]);
            }
            return (all ? d[all] : n);
        } ;
        cout << getans() << '\n';

        auto modify = [&](int x, int v) ->void {
            int p = pos[x];
            b[x] = v;
            sum[p] = 0;
            for (int i = L[p]; i <= R[p] && i <= n; i++) {
                sum[p] = gcd(sum[p], b[i]);
            }
        };
        while(q--) {
            int x, v;
            cin >> x >> v; 
            if (x > 1) {
                if (a[x - 1] > a[x] && a[x - 1] <= v) {
                    modify(x - 1, 0);
                } else if (a[x - 1] <= a[x] && a[x - 1] > v) {
                    modify(x - 1, x - 1);
                }
            }
            if (x < n) {
                if (a[x] > a[x + 1] && v <= a[x + 1]) {
                    modify(x, 0);
                } else if (a[x] <= a[x + 1] && v > a[x + 1]) {
                    modify(x, x);
                }
            }
            a[x] = v;
            cout << getans() << '\n';
        }
    }
    return 0;
}