#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
int nums[maxn];
int v[maxn];
inline int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
struct Seg{
    int val[maxn<<2];
    void pushup(int p){
        val[p]=__gcd(val[p<<1],val[p<<1|1]);
    }
    void build(int p,int l,int r){
        if(l==r){
            val[p]=v[l];
            return;
        }
        int mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }
    void update(int p,int l,int r,int np,int nv){
        if(l==r){
            val[p]=nv;
            return;
        }
        int mid=l+r>>1;
        if(np<=mid)update(p<<1,l,mid,np,nv);
        else update(p<<1|1,mid+1,r,np,nv);
        pushup(p);
    }
    int query(int p,int l,int r,int st,int en){
        if(st<=l&&en>=r){
            return val[p];
        }
        int mid=l+r>>1;
        int gd=0;
        if(st<=mid)gd=gcd(gd,query(p<<1,l,mid,st,en));
        if(en>mid)gd=gcd(gd,query(p<<1|1,mid+1,r,st,en));
        return gd;
    }
}T;
void slove(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>nums[i];
        v[i]=0;
    }
    set<int> s;
    s.insert(0);
    s.insert(1);
    for(int i=2;i<=n;i++){
        if(nums[i]<nums[i-1]){
            s.insert(i);
            auto le=lower_bound(s.begin(),s.end(),i);
            le--;
            v[i]=(i-*le);
        }
    }
    T.build(1,1,n);
    auto change=[&](int x){
        if(x>1&&nums[x]<nums[x-1]){
            //如果改变后形成了新逆转点
            if(!s.count(x)){
                auto le=lower_bound(s.begin(),s.end(),x);
                le--;
                auto ri=upper_bound(s.begin(),s.end(),x);
                T.update(1,1,n,x,x-*le);
                v[x]=x-*le;
                if(ri!=s.end()){
                    T.update(1,1,n,*ri,*ri-x);
                    v[*ri]=*ri-x;
                }
                s.insert(x);
                return 1;
            }
            return 0;
        }else{
            //如果改变后不是逆转点了
            if(x!=1&&s.count(x)){
                auto le=lower_bound(s.begin(),s.end(),x);
                le--;
                auto ri=upper_bound(s.begin(),s.end(),x);
                if(ri!=s.end()){
                    T.update(1,1,n,*ri,*ri-*le);
                    v[*ri]=*ri-*le;
                }
                T.update(1,1,n,x,0);
                v[x]=0;
                s.erase(x);
                return 1;
            }
            return 0;
        }
    };
    auto ans=[&](int x){
        int res=0;
        for(int i=1;i*i<=x;i++){
            if(x%i==0){
                if(i*i!=x)res+=2;
                else res++;
            }
        }
        return res;
    };
    int res=0;
    if(s.size()!=2)res=ans(T.query(1,1,n,1,n));
    else res=n;
    if(s.size()!=2)cout<<res<<"\n";
    else cout<<n<<"\n";
    while(q--){
        int np,nv;
        cin>>np>>nv;
        nums[np]=nv;
        int fg=0;
        fg|=change(np);
        if(np<n)fg|=change(np+1);
        if(fg)res=ans(T.query(1,1,n,1,n));
        if(s.size()!=2)cout<<res<<"\n";
        else cout<<n<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)slove();
}