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

#define ll long long 
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>

#define N 100010

set<int> factors(int x) {
    set<int> res;
    for (int i = 1; i <= sqrt(x); ++ i) {
        if (x % i == 0) {
            res.insert(i);
            res.insert(x/i);
        }
    }
    return res;
}

int cnt[N], a[N];

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        set<int> s;

        int n, q; cin >> n >> q;
        for (int i = 0; i <= n; ++ i) cnt[i] = 0;
        for (int i = 1; i <= n; ++ i) cin >> a[i];

        auto add = [&](int i) {
            assert(!s.count(i));
            for (auto x : factors(i)) ++ cnt[x];
            s.insert(i);
        };

        auto rmv = [&](int i) {
            assert(s.count(i));
            for (auto x : factors(i)) -- cnt[x];
            s.erase(i);
        };

        auto get = [&]() {
            if (s.size() == 0) return n;
            int res = 0;
            for (auto x : factors(*s.begin())) res += (cnt[x] == s.size());
            return res;
        };

        for (int i = 1; i < n; ++ i) if (a[i] > a[i+1]) add(i);
        cout << get() << '\n';

        while (q --) {
            int p, v; cin >> p >> v;
            if (s.count(p)) rmv(p);
            if (s.count(p-1)) rmv(p-1);
            a[p] = v;
            if (p < n && a[p] > a[p+1]) add(p);
            if (p > 1 && a[p-1] > a[p]) add(p-1);
            cout << get() << '\n';
        }
    }
}