#include <bits/stdc++.h>
#define For(i, l, r) for (int i=l; i<=r; ++i)
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
using namespace std;
template <typename T>
inline void read(T &x) {
    char c = getchar(); int w = 1; x = 0;
    while (!isdigit(c))
        (c == '-') && (w = -w), c = getchar();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
    x *= w;
}

const int N = 200010;
int n, q, j, v, ans[N], a[N], len[N], g[N<<2];
set<int> S;
inline int gcd(int x, int y) {
    return !y ? x : gcd(y, x % y);
}
inline void push_up(int p) {
    g[p] = gcd(g[ls(p)], g[rs(p)]);
}
inline void update(int l, int r, int p, int x, int v) {
    if (l == r) {
        len[x] += v;
        g[p] = len[x] ? x : 0;
        return;
    }
    int mid = l+r >> 1;
    if (x <= mid) update(l, mid, ls(p), x, v);
    if (x >  mid) update(mid+1, r, rs(p), x, v);
    push_up(p);
}
inline void build(int l, int r, int p) {
    if (l == r) {
        g[p] = len[l] ? l : 0; return;
    }
    int mid = l+r >> 1;
    build(l, mid, ls(p));
    build(mid+1, r, rs(p));
    push_up(p);
}
inline void add(int x) {
    if (x < *S.begin()) {
        int y = *S.begin();
        if (y == n+1) {
            update(1, n, 1, x-1, 1);
        }
        else {
            update(1, n, 1, y-1, -1);
            update(1, n, 1, x-1, 1);
            update(1, n, 1, y-x, 1);
        }
    }
    else {
        auto it = S.lower_bound(x);
        int y = *(--it);
        if (*it == n+1) {
            update(1, n, 1, x-y, 1);
        }
        else {
            update(1, n, 1, (*it)-y, -1);
            update(1, n, 1, x-y, 1);
            update(1, n, 1, (*it)-x, 1);
        }
    }
    S.insert(x);
}
inline void del(int x) {
    if (x == *S.begin()) {
        auto it = S.begin();
        ++ it;
        int y = *it;
        if (y == n+1) {
            update(1, n, 1, x-1, -1);
        }
        else {
            update(1, n, 1, x-1, -1);
            update(1, n, 1, y-x, -1);
            update(1, n, 1, y-1, 1);
        }
    }
    else {
        auto it = S.lower_bound(x);
        int y = *(--it);
        if (*it == n+1) {
            update(1, n, 1, x-y, -1);
        }
        else {
            update(1, n, 1, (*it)-x, -1);
            update(1, n, 1, x-y, -1);
            update(1, n, 1, (*it)-y, 1);
        }
    }
    S.erase(x);
}
signed main() {
    int T;
    For(i, 1, 200000) {
        for (int j=i; j<=200000; j+=i) {
            ans[j] ++;
        }
    }
    read(T);
    while (T -- > 0) {
        read(n); read(q);
        For(i, 1, n) {
            len[i] = 0;
        }
        int lst = 1;
        a[0] = 0;
        S.clear();
        S.insert(n+1);
        For(i, 1, n) {
            read(a[i]);
            if (a[i]-a[i-1] < 0) {
                len[i-lst] += 1;
                lst = i;
                S.insert(i);
            }
        }
        build(1, n, 1);
        // cout << g[1] << endl;
        if (*S.begin() == n+1) printf("%d\n", n);
        else printf("%d\n", ans[g[1]]);
        while (q -- > 0) {
            read(j); read(v);
            if (a[j]-a[j-1] >= 0 && v-a[j-1] < 0) {
                add(j);
            }
            if (a[j]-a[j-1] < 0 && v-a[j-1] >= 0) {
                del(j);
            }
            if (j+1 <= n && a[j+1]-a[j] >= 0 && a[j+1]-v < 0) {
                add(j+1);
            }
            if (j+1 <= n && a[j+1]-a[j] < 0 && a[j+1]-v >= 0) {
                del(j+1);
            }
            if (*S.begin() == n+1) printf("%d\n", n);
            else printf("%d\n", ans[g[1]]);
        }
    }
    return 0;
}