#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
template<class Info>
struct SGT {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    SGT() {}
    SGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    SGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) { // 这个就是 y 总的 pushup
        info[p] = info[l(p)] + info[r(p)];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    #undef l
    #undef r
};

struct Info {
	// 注意: 模板下标是[0,n-1],在查询修改操作时记得对应, 
//另外, query函数查询的是[l,r)  
    int num;
    Info(){
        num=0;
    }
    Info(int v){
        num=v;
    }
};
Info operator+(Info a, Info b) {
    Info c;
    c.num=gcd(a.num,b.num);
    return c;
}
int work(int x){
    int ret=0;
    for(int i=1;i<=x/i;++i){
        if(x%i==0){
            ret++;
            if((x/i)!=i) ret++;
        }
    }
    return ret;
}
void solve(){
    int n,q;
    cin >> n >> q;
    vector<int> p(n+1);
    for(int i=1;i<=n;++i) cin >> p[i];
    vector<Info> a(n);
    for(int i=1;i<=n;++i){
        if(p[i]>p[i+1]){
            a[i-1].num=i;
        }else a[i-1].num=0;
    }
    SGT<Info> sgt(a);
    if(n!=1){
        cout<<work(sgt.query(0,n).num)<<'\n';
    }
    else cout<<"1\n";
    while(q--){
        int idx,val;
        cin >> idx >> val;
        if(n==1){
            cout<<"1\n";
            continue;
        }
        if(idx==1){
            if(val>p[2]){
                sgt.modify(idx-1,1);
            }else{
                sgt.modify(idx-1,0);
            }
        }else if(idx==n){
            if(p[n-1]>val){
                sgt.modify(n-2,n-1);
            }else{
                sgt.modify(n-2,0);
            }
        }else{
            if(val>p[idx+1]){
                sgt.modify(idx-1,idx);
            }else{
                sgt.modify(idx-1,0);
            }
            if(p[idx-1]>val){
                sgt.modify(idx-2,idx-1);
            }else{
                sgt.modify(idx-2,0);
            }
        }
        p[idx]=val;
        val=sgt.query(0,n).num;
        cout<<work(val)<<'\n';
    }  
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}