#include <bits/stdc++.h>
#define int long long
using namespace std;

#define pair <int,int>   pll;
const int N = 2e5+5;
const int INF = 3e9;

int a[N];
int b[N];
int n , q;

int ans[N+10];


struct tree{
    int   l , r , sum ;
}tr[N*4];



void push_up(int u){
    if(tr[u << 1].sum == 0) tr[u].sum = tr[u << 1 | 1].sum;
    else if(tr[u << 1 | 1].sum == 0) tr[u].sum = tr[u << 1].sum;
    else tr[u].sum = gcd(tr[u << 1].sum , tr[u << 1 | 1].sum);
    //tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u,int l, int r ){
    //cout << u << ' ' << l << ' ' << r << '\n';
    if(r == l){
        tr[u] = {l,r,b[l]};
        return;
    }
    tr[u] = {l,r};
    int mid = (l + r) >> 1;
    build(u << 1,l ,mid);
    build(u << 1 | 1, mid + 1,r);
    push_up(u);
}


void modify(int u , int l, int r, int x){
    if(l > tr[u].r || r < tr[u].l) return;
    if(l <= tr[u].l && r >= tr[u].r){
        tr[u].sum  = x ;
        return;
    }
    modify(u << 1, l, r, x);
    modify(u << 1 | 1, l ,r ,x);
    push_up(u);
}

int query(int u , int x){
    if(tr[u].l >= x ) return 0;
    if(tr[u].r < x) return tr[u].sum;
    return query(u << 1, x) + query(u << 1 | 1, x);
}



void solve(){
    cin >> n  >>  q;
    ans[0] = n;
    for(int i = 0; i <= n ; i ++)
        b[i] = 0;
    for(int i = 1;i <= n ;i ++ ){
        cin >> a[i];
        if(a[i] < a[i - 1]){
            b[i] = i - 1;
        }
    }
    a[n + 1] = INF;
    build(1,1,n);
    cout << ans[tr[1].sum] << endl;
    while(q--){
        int pos, x;
        cin  >> pos >> x;
        if(a[pos] >= a[pos - 1] && x < a[pos - 1]){
            modify(1,pos,pos,pos - 1);
        }
        else if(a[pos] < a[pos - 1] && x >= a[pos - 1]){
            modify(1,pos,pos,0);
        }
        if(a[pos] > a[pos + 1] && x <= a[pos + 1]){
            modify(1,pos + 1,pos + 1,0);
        }
        else if(a[pos] <= a[pos + 1] && x > a[pos + 1]){
            modify(1,pos + 1,pos +1,pos);
        }
        a[pos] = x;
        cout << ans[tr[1].sum] << endl;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;

    for(int i = 1; i <= N ; i ++ )
        for(int j = i ; j <= N ; j += i)
            ans[j]++;

    cin >> t;
    while(t --)
        solve();
}
//