#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long 
using namespace std;
const int ma=2e5+4e4;
int T;
int n,q; 
int a[ma]; 
int num[ma],pri[ma],tot,vis[ma];  
int tmp[ma]; 
void pre_solve(){
    for(int i=2;i<ma;i++){
        if(!vis[i]) {
            pri[++tot]=i,num[i]=2;
            for(int j=i;j<ma;j+=i) vis[j]=i;  
        }      
        else {
            int x=i,y=1,cnt=0;
            while(!(x%vis[i])) x/=vis[i],y*=vis[i],cnt++; 
 //           cout<<x<<" "<<y<<" "<<cnt<<endl;
            if(x==1) num[i]=cnt+1;  
            else num[i]=num[x]*num[y];   
        }          
    }
}
struct SegmentTree{
    int gd[ma*4];
    int get_gcd(int x,int y){
        if(x<y) swap(x,y);
        if(!y) return x;
        return get_gcd(y,x%y); 
    }
    void push_up(int x){
        if((!gd[x<<1])||(!gd[(x<<1)|1])) gd[x]=gd[x<<1]|gd[(x<<1)|1]; 
        else gd[x]=get_gcd(gd[x<<1],gd[(x<<1)|1]); 
    }
    void build(int p,int l,int r){
        if(l==r) {gd[p]=tmp[l];return; }
        int mid=(l+r)>>1;
        build(p<<1,l,mid);
        build((p<<1)|1,mid+1,r); 
        push_up(p); 
    }
    void modify(int p,int l,int r,int des,int val){
        
        if(l==r){gd[p]=val; return; }
        int mid=(l+r)>>1;
        if(des<=mid) modify(p<<1,l,mid,des,val);
        else modify((p<<1)|1,mid+1,r,des,val);
        push_up(p); 
//        cout<<p<<" "<<l<<" "<<r<<" "<<des<<" "<<val<<" "<<gd[p]<<endl;
    }
}tree; 
int main(){
 //   freopen("GP.out","w",stdout);
    pre_solve() ; num[1]=1;  
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&q); num[0]=n; 
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<n;i++) if(a[i]>a[i+1]) tmp[i]=i; 
        tree.build(1,1,n); 
        printf("%d\n",num[tree.gd[1]]); 
        for(int i=1;i<=q;i++){
            int p,v; scanf("%d%d",&p,&v);
            if(a[p-1]>v) tree.modify(1,1,n,p-1,p-1); else tree.modify(1,1,n,p-1,0);
            if(v>a[p+1]&&p!=n) tree.modify(1,1,n,p,p); else tree.modify(1,1,n,p,0); 
            a[p]=v; // cout<<tree.gd[1]<<endl;
            printf("%d\n",num[tree.gd[1]]);  
        }
    }
    return 0 ;
}