#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define debug(x) cerr <<#x <<" = " << x << endl
#define fi first
#define se second
using namespace std;
const int N = 2e5 +10;
int T= 1;

int n, q, a[N];

struct node {
    int val = -1, g = -1;
    int fl = 0;
    int lb = 0, rb = 0;
    int st = 0, ed = 0;
};
node tr[N << 2];

node acc(node l, node r){
    node res;
    res.st = l.st;
    res.ed = r.ed;
    res.rb = r.rb;
    res.lb = l.lb;
    int u = a[l.ed], v = a[r.st];
    int cg = -1;
    if (u <= v){
        int len = r.lb - l.rb + 1;
        if (r.lb != r.ed && l.rb != l.st){
            cg = len;
        }
        else if (r.lb != r.ed){
            res.lb = r.lb;
        }
        else if (l.rb != l.st){
            res.rb = l.rb;
        }
        else{
            res.lb = r.lb;
            res.rb = l.rb;
        }
    }
    else{
        int llen = l.ed - l.rb + 1;
        int rlen = r.lb - r.st + 1;
        if (l.rb != l.st){
            if (cg == -1) cg = llen;
            else cg = __gcd(cg, llen);
        }
        if (r.lb != r.ed){
            if (cg == -1) cg = rlen;
            else cg = __gcd(cg, rlen);
        }
    }
    if (r.g != -1){
        if (cg != -1) cg = __gcd(cg, r.g);
        else cg = r.g ;
    }
    if (l.g != -1){
        if (cg != -1) cg = __gcd(cg, l.g);
        else cg = l.g;
    }
    res.g = cg;
    return res;
}

void bd(int p, int cl, int cr){
    if (cl == cr){
        tr[p].val = a[cl];
        tr[p].g = -1;
        tr[p].lb = tr[p].rb = tr[p].st = tr[p].ed = cl;
        if (cl == n) tr[p].fl = 1;
        return;
    }
    int mid = cl + cr >> 1;
    bd(p << 1, cl, mid);
    bd(p << 1 | 1, mid + 1, cr);
    tr[p] = acc(tr[p << 1], tr[p << 1 | 1]);
}

void upd(int x, int k, int p, int cl, int cr){
    if (cl == cr){
        a[cl] = k;
        tr[p].val = k;
        tr[p].g = -1;
        tr[p].lb = tr[p].rb = tr[p].st = tr[p].ed = cl;
        if (cl == n) tr[p].fl = 1;
        return;
    }
    int mid = cl + cr >> 1;
    if (x <= mid) upd(x, k, p << 1, cl, mid);
    else upd(x, k, p << 1 | 1, mid + 1, cr);
    tr[p] = acc(tr[p << 1], tr[p << 1 | 1]);
}

int qry(){
    int len = tr[1].lb;
    if (tr[1].g == -1) return len;
    return __gcd(len, tr[1].g);
}

void solve(){
	cin >> n >> q;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	bd(1, 1, n);
    auto get = [&](int x) -> int {
    	int res = 0;
    	for (int i = 1; i * i <= x; i ++) if (x % i == 0){
    		if (i * i == x) res ++;
    		else res += 2;
    	}
    	return res;
    };
    cout << get(qry()) << endl;
    while (q --){
    	int x, k;
    	cin >> x >> k;
    	upd(x, k, 1, 1, n);
    	cout << get(qry()) << endl;
    }
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> T;
	while(T --) solve();

	return 0;
}
/*
1
5 2
4 3 2 6 1
2 5
3 5
*/