#include<bits/stdc++.h>
using namespace std;
typedef  long long LL;
typedef pair<LL,int> PII;
const int N=2e5+10,M=1e6+10;
const int mod=1e9+7;
int INF = 1e9;

int n, m;
int phi[N],primes[N],cnt,st[N];
struct Node
{
    int l, r;
    int sum,d;
}tr[N * 4];



int gcd(int a,int b){
    if(b>a) swap(a,b);
    return b?gcd(b,a%b):a;
}

void pushup(int u)
{
    tr[u].d = gcd(tr[u << 1].d , tr[u << 1 | 1].d);
}


void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum +=d;
        if(tr[u].sum>0) tr[u].d=tr[u].r;
        else tr[u].d=0;

        //cout<<u<<" "<<tr[u].sum<<endl;
    }
    else    // 一定要分裂
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        //if(l==4) cout<<tr[5].d<<" "<<tr[4].d<<endl;
        pushup(u);
    }
}

void init(int n)
{
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i){
            phi[j]++;
        }
}

 
void solve(){
    int n,m;
    cin>>n>>m;

    vector<int> a(n+10),id(n+10);
    build(1,1,n);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        if(a[i]<=a[i+1]) continue;
        id[i]=true;

        modify(1,i,i,1); 
    }

   
    if(tr[1].d==0) cout<<n<<endl;
    else cout<<phi[tr[1].d]<<endl;
    
    while(m--){
        int x,v;
        cin>>x>>v;
        a[x]=v;
        if(x<n&&(!id[x])&&a[x]>a[x+1]){
            //cout<<1<<endl;
            modify(1,x,x,1);
            id[x]=true;
        }
        else if(x<n&&id[x]&&a[x]<=a[x+1]){
            //cout<<1<<endl;
            modify(1,x,x,-1);
            id[x]=false;
        }

        if(x>1&&id[x-1]&&a[x-1]<=a[x]){
            modify(1,x-1,x-1,-1);
            id[x-1]=false;
        }
        else if(x>1&&(!id[x-1])&&a[x-1]>a[x]){
            modify(1,x-1,x-1,1);
            id[x-1]=true;
        }


        if(tr[1].d==0) cout<<n<<endl;
        else cout<<phi[tr[1].d]<<endl;
    }
}

    
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init(N-1);
    //cout<<phi[4]<<endl;
    int T=1;
    cin>>T;
    while(T--) solve();
 
    return 0;
}