#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
using pii=pair<int,int>;
const int mod=998244353;

int n;
set<int> st;
vector<int> yin(2e5+5);

int ope() {
    if(st.empty()) return n;

    int w=*st.begin();

    for(auto i:st) {
        w=__gcd(w,i);
        if(w==1) break;
    }

    return yin[w];
}

void solve() {
    int q;
    cin>>n>>q;
    vector<int> v(n+2);
    v[0]=2e9+1,v[n+1]=0;
    for(int i=1; i<=n; i++) cin>>v[i];

    // vector<int> bad;
    st.clear();
    for(int i=1; i<n; i++) {
        if(v[i]>v[i+1]) {
            // bad.push_back(i);
            st.insert(i);
        }
    }

    // int cnt_bad=0;
    // for(int i=0; i<bad.size()-1; i++)
    //     if(bad[i+1]-bad[i]==1) cnt_bad++;

    cout<<ope()<<endl;
    while(q--) {
        int a,b; cin>>a>>b;

        //多了一个
        if(v[a-1]<=v[a]&&v[a-1]>b) {
            st.insert(a-1);
        }
        if(v[a]<=v[a+1]&&b>v[a+1]) {
            st.insert(a);
        }

        //少了一个
        if(v[a-1]>v[a]&&v[a-1]<=b) {
            st.erase(a-1);
        }
        if(v[a]>v[a+1]&&b<=v[a+1]) {
            st.erase(a);
        }

        v[a]=b;

        cout<<ope()<<endl;

    }
}


void pre() {
    for(int i=1; i<=2e5; i++) {
        for(int j=1; j<i/j; j++)
            if(i%j==0) yin[i]+=2;
        if(sqrt(i)==ceil(sqrt(i))) yin[i]++;
    }
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);

    pre();
    int t; cin>>t;
    while(t--)
        solve();

}