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

using LL = long long;

#define ls (u << 1)
#define rs (u << 1 | 1)

struct segtree {
    int n, p;
    vector<int> g;

    segtree (int _n) {
        n = _n;
        p = __bit_ceil(n + 2);
        g.assign(2 * p + 1, {});
    }

    void pushup(int u) {
        // cerr << "PUSHUP " << u << "\n";
        // cerr << format("g[{}] = gcd(g[{}] = {}, g[{}] = {}) = {}", u, ls, g[ls], rs, g[rs], gcd(g[ls], g[rs])) << "\n";
        g[u] = gcd(g[ls], g[rs]);
    }

    void cg(int u, int v) {
        // assert(u >= 1 and u <= n);
        // int uu = u;
        u += p;
        if (v > int(1E9)) {
            v = 0;
        }
        g[u] = v;
        while (u >>= 1) {
            pushup(u);
        }
        // cerr << "AFTER CG " << uu << " " << v << "\n";
        // show();
        // cerr << "\n";
    }

    // void show() {
    //     cerr << "NOW ALL THE BASE:\n";
    //     for (int i = 1; i <= n; i++) {
    //         cerr << g[i + p] << " \n"[i == n];
    //     }
    //     cerr << "NOW ALL THE TREE:\n";
    //     for (int i = 1; i <= 2 * p; i++) {
    //         cerr << g[i] << " \n"[i == 2 * p];
    //     }
    // }
};

#undef ls
#undef rs

constexpr int inf = 2E9 + 10;
constexpr int N = 2E5 + 10;
int cnt[N];

int init = []() {
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i) {
            cnt[j]++;
        }
    }
    return 0;
}();


void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a.emplace_back(inf);

    set<int> s{0, inf};
    for (int i = 1; i <= n; i++) {
        if (a[i] > a[i + 1]) s.emplace(i);
    }

    segtree tr(n + 1);
    int ls = 0;
    for (int x : s) {
        if (x) {
            tr.cg(ls + 1, x - ls);
            ls = x;
        }
    }

    auto del = [&](int x) {
        auto it = s.find(x);
        if (it == s.end()) return;
        auto it1 = prev(it), it2 = next(it);
        tr.cg(x + 1, 0);
        tr.cg(*it1 + 1, *it2 - *it1);
        s.erase(it);
    };

    auto add = [&](int x) {
        auto it1 = s.lower_bound(x);
        if (*it1 == x) return;
        auto it2 = prev(it1);
        tr.cg(*it2 + 1, x - *it2);
        tr.cg(x + 1, *it1 - x);
        s.emplace(x);
    };

    cout << (tr.g[1] == 0 ? n : cnt[tr.g[1]]) << "\n";
    while (q--) {
        int x, v;
        cin >> x >> v;
        del(x);
        del(x - 1);
        a[x] = v;
        if (a[x] > a[x + 1]) add(x);
        if (a[x - 1] > a[x]) add(x - 1);
        int res = tr.g[1];
        cout << (res == 0 ? n : cnt[res]) << "\n";
        // tr.show();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}