#include<bits/stdc++.h>
using namespace std;
const int M=2e1+5;
struct Solve{
    int a[M<<2], d[M];
    static int gcd(int x, int y){
        return y?gcd(y, x%y):x;
    }
    Solve(){
        for(int i=1;i<M;i++)
        for(int j=i;j<M;j+=i)
            d[j]++;
        
    }
    void push(int rt){
        a[rt]=gcd(a[rt<<1], a[rt<<1|1]);
    }
    void upd(int l, int r, int rt, int x, int y){
        // cerr<<"U:"<<l<<' '<<r<<' '<<rt<<' '<<x<<' '<<y<<'\n';
        if(l==r)return void(a[rt]=y);
        int mid=(l+r)/2;
        if(x<=mid)upd(l, mid, rt<<1, x, y);
        else upd(mid+1, r, rt<<1|1, x, y);
        push(rt);
        // cerr<<l<<' '<<r<<' '<<a[rt];
    }
    void add(int x){
        upd(1, M, 1, x, x);
    }
    void era(int x){
        upd(1, M, 1, x, 0);
    }
    void clear(){
        memset(a, 0, sizeof(a));
    }
    int ck(){
        if(a[1]==0)return -1;
        return d[a[1]];
    }
}Q;
int main(){
    int T,n,q;
    vector<int> a(M+1);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        for(int i=1;i<n;++i) if(a[i]>a[i+1]) Q.add(i);
        printf("%d\n",~Q.ck()?Q.ck():n);
        while(q--){
            int p, v;
            scanf("%d%d",&p,&v);
            if(p!=1&&a[p-1]>a[p]) Q.era(p-1);
            if(p!=n&&a[p]>a[p+1]) Q.era(p);
            a[p]=v;
            if(p!=1&&a[p-1]>a[p]) Q.add(p-1);
            if(p!=n&&a[p]>a[p+1]) Q.add(p);
            printf("%d\n",~Q.ck()?Q.ck():n);
        }
        Q.clear();
    }
    return 0;
}