#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 2e5 + 10, mod = 998244353, INF = 0x3f3f3f3f;
random_device rd;
mt19937_64 rng(rd());

LL n, m;
LL a[N];

template<class Info,class Tag>
struct LST{
    int n;
    vector<Info> tr;
    vector<Tag> tag;
    LST(int n) : n(n),tr(n << 2),tag(n << 2) {}
    LST(vector<Info> a) : LST(a.size() - 1){
        auto build = [&](auto self,int rt,int l,int r)->void{
            if(l == r){
                tr[rt] = a[l];
                return;
            }
            int mid = (l + r) >> 1;
            self(self,rt << 1,l,mid);
            self(self,rt << 1 | 1,mid + 1,r);
            push_up(rt);
        };
        build(build,1,1,n);
    }
    void push_up(int rt){
        tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
    }
    void apply(int rt,int l,int r,const Tag& v){
        tr[rt].apply(l,r,v);
        tag[rt].apply(v);
    }
    void push_down(int rt,int l,int r){
        int mid = (l + r) >> 1;
        apply(rt << 1,l,mid,tag[rt]);
        apply(rt << 1 | 1,mid + 1,r,tag[rt]);
        tag[rt] = Tag();
    }
    void modify(int rt,int l,int r,int x,int y,const Tag& v){
        if(x <= l && r <= y){
            apply(rt,l,r,v);
            return;
        }
        // push_down(rt,l,r);
        int mid = (l + r) >> 1;
        if(x <= mid)modify(rt << 1,l,mid,x,y,v);
        if(y > mid)modify(rt << 1 | 1,mid + 1,r,x,y,v);
        push_up(rt);
    }
    void modify(int x,int y,const Tag& v){modify(1,1,n,x,y,v);}
    Info query(int rt,int l,int r,int x,int y){
        if(x <= l && r <= y){
            return tr[rt];
        }
        // push_down(rt,l,r);
        int mid = (l + r) >> 1;
        if(x <= mid && y > mid)return query(rt << 1,l,mid,x,y) + query(rt << 1 | 1,mid + 1,r,x,y);
        else if(x <= mid)return query(rt << 1,l,mid,x,y);
        else return query(rt << 1 | 1,mid + 1,r,x,y);
    }
    Info query(int x,int y){return query(1,1,n,x,y);}
};

struct Tag{
    LL d;
    Tag(LL v = 0) {d = v;}
    void apply(Tag t){
        d = t.d;
    }
};

struct Info{
    LL g;
    Info(LL v = 0){
        g = v;
    }
    void apply(int l,int r,Tag v){
        g = v.d;
    }
};

Info operator+(Info a,Info b){
    Info c;
    c.g = __gcd(a.g, b.g);
    return c;
}

LL d[N];

void solve()
{
    LL q;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i; j <= n; j += i)d[j] += 1;
    }
    vector<Info> w(n + 1);
    for(int i = 2; i <= n; i ++)
    {
        if(a[i] < a[i - 1])w[i].g = i - 1;
    }
    LST<Info, Tag> tr(w);
    // for(int i = 1; i <= n; i ++)cout << tr.query(i, i).g << ' ';
    // cout << tr.query(1, n).g << '\n';
    LL g = tr.query(1, n).g;
    cout << d[g] << '\n';
    while(q --)
    {
        LL p, v;
        cin >> p >> v;
        if(p - 1 > 0){
            if(v < a[p - 1] && a[p] >= a[p - 1])tr.modify(p, p, Tag(p - 1));
            else if(v >= a[p - 1] && a[p] < a[p - 1]) tr.modify(p, p, Tag(0));
        }
        if(p + 1 <= n){
            if(v <= a[p + 1] && a[p] > a[p + 1])tr.modify(p + 1, p + 1, Tag(0));
            else if(v > a[p + 1] && a[p] <= a[p + 1])tr.modify(p + 1, p + 1, Tag(p));
        }
        a[p] = v;
        // for(int i = 1; i <= n; i ++)cout << tr.query(i, i).g << ' ';
        // cout << '\n';
        // cout << tr.query(1, n).g << '\n';
        g = tr.query(1, n).g;
        cout << d[g] << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    LL _T = 1;
    cin >> _T;
    while(_T --)
    {
        solve();
    }
    return 0;
}