#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

typedef long long LL;
//#define int LL
#define inl inline
const int N = 3e5 + 10;
const int M = N * 2;
//const int mod=998244353;
const int mod = 1000000007;
const double eps = 1e-8;
//const int mod=1e9+7;
typedef pair<int, int> PII;
//const int INF=0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;

void become_faster() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

#define lc u<<1
#define rc u<<1|1
struct Node {
    int l,r;
    int g;
};
Node tr[N*4];
int sa[N];
void push_up(int u) {
    tr[u].g=__gcd(tr[lc].g,tr[rc].g);
}
void build(int u,int l,int r) {
    tr[u]={l,r};
    if(l==r)return;
    int mid=(l+r)/2;
    build(lc,l,mid),build(rc,mid+1,r);
}

void modify(int u,int k,int x) {
    if(tr[u].l==tr[u].r) {
        tr[u].g=x;
        return;
    }
    else {
        int mid=(tr[u].l+tr[u].r)/2;
        if(k<=mid)modify(lc,k,x);
        else modify(rc,k,x);
        push_up(u);
    }
}
int query(int u,int l,int r) {
    if(tr[u].l>=l&&tr[u].r<=r) {
        return tr[u].g;
    }
    else {
        int mid=(tr[u].l+tr[u].r)/2;
        int res=0;
        if(l<=mid)res=__gcd(res,query(lc,l,r));
        if(r>mid)res=__gcd(res,query(rc,l,r));
        return res;
    }
}
int find_first_num(int u,int l,int r) {
    if(tr[u].l>r||tr[u].r<l)return -1;
    if(tr[u].l>=l&&tr[u].r<=r&&!tr[u].g)return -1;
    if(tr[u].l==tr[u].r)return tr[u].l;

    int res=-1;
    res=find_first_num(lc,l,r);
    if(res==-1)res=find_first_num(rc,l,r);
    return res;
}
int find_last_num(int u,int l,int r) {
    if(tr[u].l>r||tr[u].r<l)return -1;
    if(tr[u].l>=l&&tr[u].r<=r&&!tr[u].g)return -1;
    if(tr[u].l==tr[u].r)return tr[u].l;

    int res=-1;
    res=find_last_num(rc,l,r);
    if(res==-1)res=find_last_num(lc,l,r);
    return res;
}
int f[N];
void init() {
    for(int i=1;i<=200000;i++) {
        for(int j=1;j*j<=i;j++) {
            if(i%j==0) {
                f[i]++;
                if(i%(i/j)==0&&j!=i/j)f[i]++;
            }
        }
    }
}
void solve() {
    cin>>n>>m;
    f[0]=n;
    for(int i=1;i<=n;i++) {
        cin>>sa[i];
    }
    build(1,1,n);
    int last=1;
    for(int i=1;i<=n;i++) {
        if(sa[i]<sa[i-1]) {
            modify(1,i,i-last);
            last=i;
        }
    }
    auto debug=[&]() {
        cerr << "debug: " << "\n";
        for (int i = 1; i <= n; i++) {
            cerr << query(1, i, i) << " ";
        }
        cerr << "\n";
    };
    //debug();
    int res=query(1,1,n);
    //if(res==0)res=n;
    //cout<<"f: "<<f[res]<<"\n";
    //cout<<"res="<<res<<"\n";
    cout<<f[res]<<"\n";
    while(m--) {
        int p,x;
        cin>>p>>x;
        sa[p]=x;
        if(sa[p]>=sa[p-1]) {
            if(p+1<=n&&sa[p+1]>=sa[p])modify(1,p+1,0);
            modify(1,p,0);
            if(p+1<=n&&sa[p+1]<sa[p])modify(1,p+1,1);
            int p1=find_last_num(1,1,p);
            if(p1==-1)p1=1;
            if(p+1<=n) {
                int p2=find_first_num(1,p+1,n);
                if(p2!=-1)modify(1,p2,p2-p1);
            }
        }
        else {
            if(p+1<=n&&sa[p+1]>=sa[p])modify(1,p+1,0);
            if(p-1>=1) {
                int p1 = find_last_num(1, 1, p - 1);
                if (p1 == -1)p1 = 1;
                modify(1, p, p - p1);
            }
            if(p+1<=n) {
                int p2=find_first_num(1,p+1,n);
                if(p2!=-1) {
                    modify(1,p2,p2-p);
                }
            }
        }
        //debug();
        res=query(1,1,n);
        //if(res==0)res=n;
        //cout<<"f: "<<f[res]<<"\n";
        //cout<<"res="<<res<<"\n";
        cout<<f[res]<<"\n";
    }
}
/*
1
5 2
4 3 2 6 1
2 5
3 5

1
5 2
4 5 2 6 1
2 5
3 5

1
5 2
4 5 5 6 1
2 5
3 5
 */
signed main() {
    become_faster();
    int T = 1;
    //T=read();
    init();
    cin>>T;
    //for(int i=1;i<=100;i++)solve(i);
    while (T--) solve();
    return 0;
}