#include<bits/stdc++.h>

using namespace std;

#define ull unsigned long long
#define ll long long
#define lowbit(x) (x)&(-x)
//#define int long long
//#define double long double 
const int N = 1e6 + 5;
const ll base = 131;
const ll mod = 998244353;
int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
void solve() {
    int n,q;
    cin>>n>>q;
    vector<int>a(n+1);
    for(int i=1;i<=n;++i) cin>>a[i];
    vector<int>b(n+1);
    for(int i=1;i<n;++i){
        if(a[i]>a[i+1]) b[i]=i; 
    }
    vector<int>tree(4*n+9);
    auto buildtree=[&](auto self,int i,int s,int t){
         if(s==t){
            tree[i]=b[s];
            return ;
         }
         int mid=s+t>>1;
         self(self,i<<1,s,mid);
         self(self,i<<1|1,mid+1,t);
         tree[i]=gcd(tree[i<<1],tree[i<<1|1]);
    };
    buildtree(buildtree,1,1,n);
    auto update=[&](auto self,int i,int s,int t,int x,int k){
         if(s==t&&s==x){
            tree[i]=k;
            return ;
         }
         int mid=s+t>>1;
         if(x<=mid) self(self,i<<1,s,mid,x,k);
         if(x>mid) self(self,i<<1|1,mid+1,t,x,k);
         tree[i]=gcd(tree[i<<1],tree[i<<1|1]);
    };
    auto getas=[&](int now){
        int cnt=0;
        for(int i=1;i*i<=now;++i){
            if(now%i==0){
                ++cnt;
                if(i*i!=now) cnt++;
            }
        }
        return cnt;
    };
    cout<<getas(tree[1])<<'\n';
    //cerr<<1<<'\n';
    while(q--){
        int u,v;
        cin>>u>>v;
        a[u]=v;
        if(u>1){
            if(a[u]<a[u-1]) b[u-1]=u-1;
            else b[u-1]=0;
        }
        if(u<n){
           if(a[u]>a[u+1]) b[u]=u;
           else b[u]=0;    
        }
        if(u>1)update(update,1,1,n,u-1,b[u-1]);
        if(u<n)update(update,1,1,n,u,b[u]);
        cout<<getas(tree[1])<<'\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}